2014-06-10

IOI系ページまとめ

コンテスト系その他

OI系の問題はなかなかジャッジに搭載されてくれないので、探すのは意外と大変です。そこでIOI対策に役に立つページたちをまとめます。

情報オリンピック日本委員会（http://www.ioi-jp.org/）
- 言わずと知れたJOIのサイト。これがないと予選に出れません。

http://www.ioinformatics.org/history.shtml
- IOIの問題、ランキング、テストデータ、そして年によっては解法が載っています。

http://stats.ioinformatics.org/olympiads/
- 昔の結果などを詳しく知りたい人に便利

http://www.tani.cs.chs.nihon-u.ac.jp/ioi/
- 谷先生のページで、昔のIOIの問題の日本語訳、解説の日本語訳、データセットがあります（最近のはJOIのサイトにあります）

http://atcoder.jp/
- JOI春合宿のオンラインジャッジ（JOIOJ）,JOI春合宿2013、2012年のオープンコンテスト、APIO2012、IOIer Japan Programming Contest などがまだジャッジできます

https://wcipeg.com/problems/cat%3Dioi%2Cshow%3D50
- 入るときにブラウザが騒ぎますが多分大丈夫です。Categoryから、IOI,COCI,NOI(中国のOIっぽい),USACO の問題の英語とジャッジがあります。IOIとUSACOはちゃんと更新されている模様。

http://www.hsin.hr/coci/announcement.html
- クロアチアのOIで、毎年7回ぐらいオープンコンテストを開いています。

http://acm.tongji.edu.cn/contestproblems?pid=&title=&source=CEOI&setter=
- SourceにCEOI,BOIと入れるとそこそこの数の少し古い問題が出てきます。BOIはBalkanかBalticかどっちかは知りません。あとページを読み込むたびにブラウザが騒ぐのが難点。

http://www.spoj.com/OI/problems/main/
- SPOJのOI系問題が集まったページ。ジャッジが遅いのとレスポンスがおかしい（WAとかREとかじゃなくて、点数だけが帰ってくる）のが難点。
http://www.codechef.com/
- ChefのLunchtime系コンテストはIOI形式で開かれています。

http://www.usaco.org/
- USACOの最近のページ。たまに代表選抜コンテストなどをやってたりします。教育的良問も多いし、ソースコード付きのEditorialも充実していて、さらに幅広いレベルの問題があります。また、最近の問題はジャッジしてくれます。

http://poj.org/problemlist
- Search in Sourceにして、SourceにUSACO,IOI,Romania OI, Croatia OI,CEOIと入れると問題が出てきます。

http://main.edu.pl/en
- 最近少し有名になってきた（？）Main.edu.pl 　Task archiveの中に大量にレベルの高い問題があります。比較的数学ゲー系が多い印象？ですがPOIは木やDPがとても多いです（それでも少し新鮮な感じがするかも）

http://oi.edu.pl/l/40/
- POIの問題のテストデータ、解法のソースコードがあります。ソースコードはポーランド語の変数、関数がよくあります。

http://wikiwiki.jp/poiwiki/?FrontPage
- 早速放置されかけてるけど。POIの邦訳と解説を目指したサイト

http://cms.ioi-jp.org/
- JOIのCMSのページ。過去問のジャッジはできませんが問題文とテストデータがおいてあります。

http://www.acmicpc.net/category/
- 韓国のOJで、カテゴリ「Olympiad」からいろんなコンテストの問題が解ける（「삭제」となっているものは解けないっぽい）　問題文は韓国語だけど、APIOのジャッジ、COCIのジャッジとしても使えそう

他にオススメなどあったらコメントしてください

2014-05-16

今年の目標

雑記

そういえば作ってなかったので。

必須目標

CF Rating で2350をつける
TC Rating で2550をつける
進級

これぐらいは

上の状態で年越し
上+100ぐらいはつける（どっちも）
（あれば）国内コンテストで5位以内 ex.天プロ
不可を出さない

やりたいなあ

国際オンサイト（TCO,GCJ,Yandex.Algo etc..）に出る
言葉遊びでｳｪｲwする

2014-03-31

XIX OI Festival

POI

問題分はこちら
http://wikiwiki.jp/poiwiki/?%CC%E4%C2%EA%B0%EC%CD%F7%2F%C2%E819%B2%F3%2FFestival%20%CC%E4%C2%EA

人iの到着時刻をCiとおくと、
aはbより1秒早い、という条件は
Ca=Cb-1
つまり、
Ca-Cb<=-1
Cb-Ca<=1
と表せる。

cはdより早い、という条件は、
Cc-Cd<=0
と表せる。

上の条件を、牛ゲー風にグラフにする。
(Ca-Cb<=-1 なら、b->aにコスト-1の辺を張る)
強連結成分ごとにグラフを分けて、それぞれの成分ごとの答えの和を求めればよい。
(別の強連結成分の人間の到着時刻は、自由に引き離せる)
上の条件を満たす中で、到着時刻の最大の差が強連結成分ごとの答え。
(強連結成分内での到着時刻に差があるとき、その間の整数の到着時刻を取る人間は常にいる)
これは、グラフの2点間の最短経路の長さの最大値。(蟻本Layoutみたいな感じで)
条件を満たせないときは、負閉路ができている。

強連結成分分解、負閉路検出、最短経路はすべてWarshall Floyd風にO(N^3)でできる。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
using namespace std;
static const int INF =500000000; 
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;

int g[605][605];
bool reach[605][605];//到着可能か
int n,m1,m2;

int done[605],mark[605];
int main(){
	cin>>n>>m1>>m2;
	REP(i,n) REP(j,n) g[i][j]=INF;
	REP(i,n) REP(j,n) g[i][i]=0;
	REP(i,m1){
		int a,b;cin>>a>>b;--a;--b;
		chmin(g[a][b],1);
		chmin(g[b][a],-1);
		reach[a][b]=reach[b][a]=true;
	}
	REP(i,m2){
		int a,b;cin>>a>>b;--a;--b;
		chmin(g[b][a],0);
		reach[b][a]=true;
	}

	REP(i,n) REP(j,n) REP(k,n){
		reach[j][k]|=(reach[j][i]&reach[i][k]);
		chmin(g[j][k],g[j][i]+g[i][k]);
	}

	REP(i,n) if(g[i][i]<0){
		puts("NIE");
		return 0;
	}
	
	int res=0;
	REP(i,n) if(!done[i]){
		memset(mark,0,sizeof(mark));

		REP(j,n) if(reach[i][j] && reach[j][i]) done[j]=mark[j]=1;
//相互に到着可能<->同じ強連結成分
		
		int tmp=0;
		REP(j,n) if(mark[j]) REP(k,n) if(mark[k]) chmax(tmp,g[j][k]);
//最大の最短経路の距離
		res+=tmp+1;
	}
	printf("%d\n",res);

	return 0;
}

2013-09-14

PCK2013 予選 9

PCK

幾何ライブラリなくて焦ったけど大丈Vだった。

左端の取る点を固定して、反時計回りに取っていく。
dp[今までの頂点数][二つ前の頂点][一つ前の頂点]=面積最小値
とすると頑張って更新できる。O(N^5)
この値から、すべての答えをあらかじめ求めておく。
出力の順番を勘違いしてたので、ちょっと終盤頭悪いことになってます

#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<cstdio>
#include<complex>
 
#define REP(i,m) for(int i=0;i<m;++i)
#define REPN(i,m,in) for(int i=in;i<m;++i)
#define ALL(t) (t).begin(),(t).end()
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
 
#define prl cerr<<__LINE__<<" is called"<<endl
#define dump(x) cerr<<#x<<" = "<<x<<endl
 
using namespace std;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef pair<int,int> pi;
typedef long long lint;
typedef complex<lint> P;
const lint INF2=1e18;
 
P p[50],q[50];
int n;
bool cmp(const P& a,const P& b){
    if(a.real()!=b.real()) return a.real()<b.real();
    return a.imag()<b.imag();
}
lint cross(P a,P b){
    return a.real()*b.imag()-a.imag()*b.real();
}
int ccw(P a,P b,P c){
    b-=a;c-=a;
    if(cross(b,c)<0) return -1;//clockwise
    if(cross(b,c)>0) return 1;//counter-clockwise
    return 0;
}
 
lint getarea(P a,P b,P c){
    return abs(cross(b-a,c-a));
}
 
 
int id[55],rev[55];
lint minarea[55];
vector<int> vs[55];
lint dp[55][55][55];
int back[55][55][55];
void solve(int n,int add){
    REP(i,n+1) REP(j,n+1) REP(k,n+1) dp[i][j][k]=INF2;
    REPN(i,n,1) {
        dp[2][0][i]=0;
    }
 
    REP(i,n+1) REP(j,n) REP(k,n) if(dp[i][j][k]<INF2){
        REPN(l,n,1) if(j!=l && k!=l){
            if(ccw(q[j],q[k],q[l])==1 && ccw(q[k],q[l],q[0])>=0){
            lint nval=dp[i][j][k]+getarea(q[0],q[k],q[l]);
            if(dp[i+1][k][l]>nval){
                dp[i+1][k][l]=nval;
                back[i+1][k][l]=j;
            }
            }
        }
        if(minarea[i]>dp[i][j][k]){
            vector<int> tmp;
            tmp.pb(rev[k+add]);
            tmp.pb(rev[j+add]);
            int k2=k,j2=j,i2=i;
            while(j2!=0){
                int last=back[i2][j2][k2];
                k2=j2;
                j2=last;
                tmp.pb(rev[j2+add]);
                --i2;
            }
 
            minarea[i]=dp[i][j][k];
            reverse(ALL(tmp));
            vs[i]=tmp;
        }
    }
 
 
}
 
P prev[55];
int main(){
    cin>>n;
    REP(i,n) cin>>p[i].real()>>p[i].imag(),q[i]=prev[i]=p[i];
    REP(i,n+1) minarea[i]=INF2;
 
    sort(p,p+n,cmp);
    REP(i,n){
        REP(j,n) if(q[i]==p[j]) id[i]=j;
    }
    REP(i,n) rev[id[i]]=i;
    REP(i,n){
        REPN(j,n,i) q[j-i]=p[j]-p[i];
 
        solve(n-i,i);
    }
     
    REPN(s,n+1,3) if(minarea[s]!=INF2){
        REP(i,s){
            int fail=0;
            REP(j,s) if(prev[vs[s][i]].imag()>prev[vs[s][j]].imag() 
            || (prev[vs[s][i]].imag()==prev[vs[s][j]].imag() &&
                    prev[vs[s][i]].real()>prev[vs[s][j]].real())){
                fail=1;
            }
            if(!fail){
                rotate(vs[s].begin(),vs[s].begin()+i,vs[s].end());
                break;
            }
        }
    }
 
    int q;cin>>q;
    REP(hoge,q){
        int m;cin>>m;
        if(minarea[m]==INF2){
            puts("NA");
        }else{
            REP(j,m) printf("%d%c",vs[m][j]+1,j==m-1?'\n':' ');
        }
    }
 
    return 0;
}

2013-03-11

個人的良問リスト

コンテスト系その他

少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます
良問、というより解く価値のある問題、といった方が正確かもしれません
2ヶ月ごとぐらいにアップデートする予定です
問題のリンクが貼ってあり、右に白い文字で解法の要素が単語で書いて有ります(マウスで囲うと見えます)
解法の要素は自分にわかるように作ったので不明な点があるかもしれません
☆は僕が初見では解けなかった問題たちです
一部、キーワードが変なひらがなになってるのがありますが、それははてなのキーワードに引っ掛けないためです

キーワードのみではわからないのも多いと思うのでなんか気になったら聞いてください(僕は全部解いているはずです)

問題たちには偏りがあります。今のところCF,USACO,Polish OIがほとんどです

誤解を招きそうな表現-> O(N)は問題の本質部分がO(N)で解けるということを言ってて、全体の計算量がO(N)というのを示すわけではないです

追加 5/5

http://www.codeforces.com/contest/280/problem/C 木確率
http://main.edu.pl/en/archive/oi/18/imp 貪欲 ☆
http://main.edu.pl/en/archive/oi/18/met BIT 二分探索
http://main.edu.pl/en/archive/oi/18/pro フロー貪欲 X最小費用流 ☆
http://main.edu.pl/en/archive/oi/17/kor 調和きゅうすうローリングハッシュ
http://www.codeforces.com/contest/283/problem/C DP
http://www.codeforces.com/contest/283/problem/E セグメント木数え上げ ☆
http://joisc2013-day3.contest.atcoder.jp/tasks/joisc2013_cake 分割統治実はO(NlogN) or セグメント木 ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_communication グラフ木 Union-find 隣り合ったものがすべて繋がっていればOK ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_collecting セグメント木包除数え上げ
http://joisc2013-day2.contest.atcoder.jp/tasks/joisc2013_mascots DP 数え上げ縦に伸ばす・横に伸ばすのみで十分
http://main.edu.pl/en/archive/oi/17/klo O(N) ☆ 取りうるものは階段上になる一部のみ
http://www.codeforces.com/contest/277/problem/E 最小費用流 O(N^3logN)
http://main.edu.pl/en/archive/oi/17/owc 円環しゃくとり DP O(N^3)
http://main.edu.pl/en/archive/oi/17/tel 貪欲グラフ O(N+M) ☆
http://www.codeforces.com/contest/286/problem/A 実験 O(N)
http://www.codeforces.com/contest/286/problem/B 調和きゅうすうほとんどの場所は動かない O(NlogN)
http://www.codeforces.com/contest/286/problem/D 区間重複を取り除く->イベント O*1
http://main.edu.pl/en/archive/oi/16/gas 木貪欲葉から貪欲に切り離す O(NK)
http://main.edu.pl/en/archive/oi/16/baj 回文の中心を決めて、幅優先。2ステップ一気にやろうとするとTLE O(NM+DM)
http://main.edu.pl/en/archive/oi/16/kon DP 1ステップに複数の移動候補がある方が、却ってメモリ面で優秀 O(N^2K)
http://main.edu.pl/en/archive/oi/16/arc リスト省メモリ STD::リスト使える　(広義)減少列に分割して、それぞれのステップで消すのは最初の減少列の最後いれれーたで頑張る ☆
http://main.edu.pl/en/archive/oi/16/lyz セグメント木ある区間の和が、区間の長さをD増やしても入らないならOUT と言い換えられる　O((n+m)log n) ☆
http://main.edu.pl/en/archive/oi/16/slw 文字列　検索　貪欲？　f^k(0)に含まれるなら、f^(k-1)(0)で求められる文字列も定まる　これをk=0になるまで繰り返す。途中で0が挟まったりするとアウト ☆
http://main.edu.pl/en/archive/oi/16/wsp 幾何貪欲スタックある街からは、そこから一番首都側にいける辺以外は使う必要がない最初は円環状に回るのをどんどんショートカットしていく感じ O(n+mlogm) ☆
http://main.edu.pl/en/archive/oi/15/blo dfs lowlink 関節点のみ、自明コスト以外に足す必要がある low[dst]>=pre[v] のとき、dstの先は上に戻れないので、通る必要のある組み合わせをたす O(E)
http://main.edu.pl/en/archive/oi/15/rob BFS imos法タコ型状なので、上と下に分割する。上に凸な三角形っぽいものに分割すると、上から平面走査していき、一番後まで邪魔になるのは一番下にあるX これを利用してimos法などを使い、どこに入れないかを求める。　あとはBFSだけ O(N^2) ☆
http://main.edu.pl/en/archive/oi/15/bbb デック　スライド最小値累積和 k回revolveした時を考えると、その時預金額が最も少ないときから、いくつ変更するかが分かる O(N)
http://www.codeforces.com/contest/295/problem/D 数え上げ DP imos法 dp[高さ][幅] で、ピラミッド状の形をいくつ作れるかを数える遷移で、一次関数状に値が増える感じの足し方をするが、imos法を2回やればOK caveの形は、最後の膨らんだところで分割して、ここでも多重imos法を使ってがんばる O(NM)
http://www.codeforces.com/contest/295/problem/E DP セグメント木座標圧縮列で持たずに、どこの場所がONになってるかを考える更新も、(左ノードのコスト)+(左ノードが左の右端まで行く値)*(左ノードの数)+(左ノードの数)(右ノードの数)(左と右の間隙) ... のようにすればいける O(MlogN)
http://www.codeforces.com/contest/150/problem/E 木　セグメント木重心分解二分探索定数倍　中央値k以上にできるか、という二分探索をする。パスの中で、上方に寄与する辺が半分以上ならよい。重心分解をして、重心からの距離がある範囲の中で最大に上方に寄与する頂点を求めたくなる。これはセグメント木で実現できる O(Nlog^3n) logはひとつ外れる。
http://main.edu.pl/en/archive/oi/14/drz セグメント木　コスト付けで問題になるのはそれ自体の値、左、右の値交換先の木の高さをxとして隣接する2つのコストの和のグラフを作ると、3つのパートから成る。　木の高さでソートし、常に、交換相手にとって交換する木が、3つのパートのどこに位置するかを持っておく。また、交換する木にとって相手が3つのどのパートにあるかも場合分けして求める。これらをセグメント木を使って行う。端の場合・隣接する2つを交換する場合に注意。 O(NlogN)
http://main.edu.pl/en/archive/oi/14/grz φ関数整数　φ(k)*(a/k)*(b/k) の合計を求めることになる。 kを1...√b まで調べ、そのあとはb/kの値別に、kが√b以上のものを調べる。 O(N*B^0.5)
http://main.edu.pl/en/archive/oi/14/grz 素因数ぶんかい文字列クエリ長さLの範囲のとき、Lの素因数について独立に切れるかどうか考えればよいまた、Kの長さでに切れるかどうかは、 [0,L-K)==[K,L)を調べればよい O(NloglogN+QlogN)

POIとかむっちゃ難しいのでちゅうい
良問の基準も人によって違うので注意しましょう僕は比較的甘いほうだと思うのでそこまで良くないのも混ざってるかもしれません

*1:Q+N)*log(Q+N

2013-02-02

Codeforces #165 div1-D Maximum Waterfall

http://www.codeforces.com/contest/269/problem/D

問題概要

高さ、左端、右端の決まった棚がN個ある。
i番目の棚の高さ、左端、右端をそれぞれhi,li,riとおく。

ある棚iから、ある棚jに水を流せる時、

max(li,lj)＜min(ri,rj) つまり棚iと棚jが上から見た時重なっていて、
hj＜hi で
棚iから棚kに水を流せて、棚kから棚jへ水を流せるようなkが存在しない

という3つが満たされている。

ある棚iからある棚jに水を流すとき、流せる量は、min(ri,rj)-max(li,lj)

最も上の長さが無限の棚から、最も下の長さが無限の棚に、なるべく多く一本の水を流したい
水を流す経路の流量は、棚から棚へ流せる水の量の最小値

流せる水の最大値を求めよ

N<=10^5
|li,ri|<=10^9
hi<=10^9

方針

左右の座標の値をまずは圧縮

棚を下から順番に見ていく
dp[i]:=棚iから水を流すときの流せる水の最大値

棚iの範囲で、棚iより下の棚たちを見下ろした時に見える棚(棚jとおく)すべてについて、
棚jに棚iから水を下ろせるか考える。

棚jに水を下ろせるのは、棚iの範囲とかぶっている棚jの範囲がすべて見えるとき
この時、dp[i]=max(dp[i],min(dp[j],(iとjの被っている部分の長さ)))
と更新できる。

更新が終わったら、上から見た時に見える棚に棚iを追加する
上から見た時に見える棚の管理には、set＜pair＜int,int> >などを使えばできる

dp[最も上の棚の番号] が答え

棚iから下へ見える棚は最大N個有りそうなので、O(N^2)かO(N^2logN)のような気がするが、
もしある区間を見下ろせたなら、その区間はiによって覆われるので棚iによってしか見下ろされない
更新が終わると、棚iの区間、棚iの両側にもともとあり、途切れることとなった区間の3つが追加される

区間は1回しか見下ろされないので、O(N * logN)ぐらいで終了する。

下のコードのdoitは、上の方針と少し違い、
[l,r)の範囲で最も上にある区間をセグメント木により探し、その区間で更新できるか調べ、
最も上にある区間以外の残りの範囲について再帰的に調べています

実装量は多いですが挿入削除の面倒なことが少ないかと思います

using namespace std;
static const int INF =1000000005;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
struct segtree{
	int val[800005],all[800005];
	int n;
	void init(int n_){
		n=1;
		while(n<n_) n<<=1;
		for(int i=0;i<n*2;++i) val[i]=-1,all[i]=-1;
	}
	int query(int a,int b,int i,int l,int r){
		if(a<=l && r<=b) return val[i];
		if(b<=l || r<=a) return -1;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		return max(query(a,b,i*2+1,l,md),query(a,b,i*2+2,md,r));
	}
	void set(int a,int b,int i,int l,int r,int v){
		if(a<=l && r<=b){
			val[i]=v;
			all[i]=v;
			return;
		}
		if(b<=l || r<=a) return;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		set(a,b,i*2+1,l,md,v);
		set(a,b,i*2+2,md,r,v);
		val[i]=max(val[i*2+1],val[i*2+2]);
	}
};
segtree seg;
pair<int,pi> wall[100005];
int zip[200005];
int n,t;
int dp[100005];

void doit(int l,int r,int who,int excL=1,int excR=1){
//excL/excR 左/右に伸びていてよいかどうか(1ならOK)
	int id=seg.query(l,r,0,0,seg.n);
	if(id==-1){//最も下の棚専用
		seg.set(l,r,0,0,seg.n,who);
		dp[who]=zip[r]-zip[l];
		return;
	}
	int l2=wall[id].second.first,r2=wall[id].second.second;
	if(!(l2<l && excL==0) && !(r<r2 && excR==0)){
		dp[who]=max(dp[who],min(dp[id],min(zip[r],zip[r2])-max(zip[l],zip[l2])));
	}

	if(l<l2) doit(l,l2,who,excL,0);
	if(r2<r) doit(r2,r,who,0,excR);
}

int main(){
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;++i){
		int a,b,h;scanf("%d%d%d",&h,&a,&b);
		zip[i*2]=a;
		zip[i*2+1]=b;
		wall[i]=make_pair(h,make_pair(a,b));
	}

	zip[n*2]=-INF;
	zip[n*2+1]=INF;
	sort(zip,zip+n*2+2);
	int zn=unique(zip,zip+n*2+2)-zip;
	wall[n++]=make_pair(0,make_pair(-INF,INF));
	wall[n++]=make_pair(t,make_pair(-INF,INF));
	for(int i=0;i<n;++i){
		wall[i].second.first=lower_bound(zip,zip+zn,wall[i].second.first)-zip;
		wall[i].second.second=lower_bound(zip,zip+zn,wall[i].second.second)-zip;
	}
	sort(wall,wall+n);

	seg.init(zn);
	for(int i=0;i<n;++i){
		int h=wall[i].first,l=wall[i].second.first,r=wall[i].second.second;

		doit(l,r,i);
		seg.set(l,r,0,0,seg.n,i);
	}
	printf("%d\n",dp[n-1]);


	return 0;
}

2013-02-02

Codeforces #165 div1-C,div2-E Flawed Flow

http://www.codeforces.com/contest/269/problem/C

問題概要

N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである
ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない)
フローが成り立つようにそれぞれの辺について向きを決めよ
ただし、得られるフローはサイクルを含んではいけない
グラフは連結で、答えは必ず存在する

N,M<=2*10^5
1<=流量<=10^4

方針

サイクルを含まないので、得られるフローのグラフは、トポロジカル順序をつけることが出来る。
ソースは最も順序の早い点で、そこから出る辺はすべてソースと逆向きに流れている
ここで、ソースに隣接する点のうち、どれかはトポロジカル順序がソースの次に小さいはずである
トポロジカル順序がソースの次に小さい頂点をvと置くと、vにはソース以外からフローが流れこまないので、
ソースから向かう辺の流量と、それ以外のつながれた辺の流量が等しいはず
逆に、ソース->vの辺以外はvから流れださなければフローが成立しないので、
ソースの時と同様にvから流す

残った頂点の中でトポロジカル順序が最も早いものが必ず見つかるはずなので、これを繰り返せば答えが求まる。

ソース、シンクの扱いに注意

O(N+M)

using namespace std;
static const int INF =500000000;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n,m;
vector<pair<pi,pi> > g[200005];
int in[200005],flow[200005];
int vis[200005];
int ans[200005];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
		g[a].push_back(make_pair(make_pair(b,c),make_pair(0,i)));
		g[b].push_back(make_pair(make_pair(a,c),make_pair(1,i)));
		flow[a]+=c;
		flow[b]+=c;
	}

	memset(ans,-1,sizeof(ans));

	queue<int> q;q.push(0);
	while(!q.empty()){
		int v=q.front();q.pop();
		vis[v]=1;
		for(int i=0;i<g[v].size();++i){
			pair<pi,pi>& e=g[v][i];
			if(vis[e.first.first]) continue;
			in[e.first.first]+=e.first.second;
			ans[e.second.second]=e.second.first;
			if(in[e.first.first]==flow[e.first.first]/2 && e.first.first!=n-1) q.push(e.first.first);
		}
	}


	for(int i=0;i<m;++i) printf("%d\n",ans[i]);





	return 0;
}

hogloidのブログ

へなちょこ

IOI系ページまとめ

今年の目標

必須目標

これぐらいは

やりたいなあ

XIX OI Festival

PCK2013 予選 9

個人的良問リスト

Codeforces #165 div1-D Maximum Waterfall

問題概要

方針

Codeforces #165 div1-C,div2-E Flawed Flow

問題概要

方針