Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2096-4d8b91e8
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #75 DIV1 C問題/DIV2 E問題 - Ski Base (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 C問題 (1500pt)
Codeforces Beta Round #72 DIV2 E問題 (2500pt)
Problem description

問題概要

最初は枝の無いノード数N (10^5以下) のグラフ.
M回 (10^5) 枝を加える操作を行う.
各操作の後に,以下の条件を満たす枝の集合の数をmod 1000000009で求める問題.
 空ではない
 その枝を全部1回ずつ使って閉路がいくつかできる (連結である必要がない)

解法

枝を使うか使わないか,mod 2の世界での連立一次方程式に帰着することを考える.
連立一次方程式は,各ノードの次数がmod 2で0となること.
すると,2^一次従属な条件の数 - 1が答えになる.-1は空集合を除くため.
一次従属な条件は,すでに連結なノード対に枝を加えたときに1つ増える.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000009

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int main(){
  int i,j,k,l,m,n;
  int ind[110000];
  int res;

  while(scanf("%d%d",&n,&m)==2){
    unionInit(ind,n);
    res = 1;
    while(m--){
      scanf("%d%d",&i,&j); i--; j--;
      if(unionConnect(ind,i,j)==0) res = (res*2)%M;
      printf("%d\n",(res+M-1)%M);
    }
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2096-4d8b91e8
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。