結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-16 11:12:18 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,204 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 85,120 KB |
実行使用メモリ | 51,220 KB |
最終ジャッジ日時 | 2024-06-29 14:37:27 |
合計ジャッジ時間 | 29,929 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 5 ms
11,432 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 6 ms
11,308 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 28 ms
15,860 KB |
testcase_31 | AC | 295 ms
51,220 KB |
testcase_32 | AC | 229 ms
40,920 KB |
testcase_33 | AC | 128 ms
29,512 KB |
testcase_34 | AC | 224 ms
40,004 KB |
testcase_35 | AC | 128 ms
30,316 KB |
testcase_36 | AC | 28 ms
15,596 KB |
testcase_37 | AC | 39 ms
17,432 KB |
testcase_38 | AC | 246 ms
42,724 KB |
testcase_39 | AC | 87 ms
26,232 KB |
testcase_40 | AC | 74 ms
23,604 KB |
testcase_41 | AC | 162 ms
33,960 KB |
testcase_42 | AC | 100 ms
26,524 KB |
testcase_43 | AC | 126 ms
29,616 KB |
testcase_44 | AC | 92 ms
25,520 KB |
testcase_45 | AC | 71 ms
22,572 KB |
testcase_46 | AC | 31 ms
16,164 KB |
testcase_47 | AC | 22 ms
14,400 KB |
testcase_48 | AC | 259 ms
42,448 KB |
testcase_49 | AC | 12 ms
12,724 KB |
testcase_50 | AC | 5 ms
11,300 KB |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | TLE | - |
07_evil_01.txt | -- | - |
07_evil_02.txt | -- | - |
ソースコード
//時間計測用 //構築未実装 #include <iostream> #include <stdio.h> #include <vector> #include <algorithm> #include <assert.h> #include <stdlib.h> #include <memory.h> #include <queue> #include <time.h> using namespace std; #define ll long long #define INF 1000000000000000000 ostream& operator<<(ostream& os,queue<ll> a){ while(!a.empty()){ ll t=a.front(); a.pop(); os<<t<<" "; } return os; } ll my_min(ll x,ll y){ if(x>y)return y; return x; } struct edge3{ ll to,cap,rev; }; ostream& operator<<(ostream& os,edge3& a){ return os<<a.to<<" "<<a.cap<<" "<<a.rev; } ostream& operator<<(ostream& os,vector<edge3>& a){ for(edge3 i:a){ os<<i<<"\n"; } return os; } //typedef struct Dinic{ //const ll INF=1000000000000000000; const ll MAX_V=200010; /* vector<edge3>* G; ll* level; ll* iter; */ vector<edge3> G[200010]; ll level[200010]; ll iter[200010]; //Dinic(){} /* Dinic(ll max_v){ MAX_V = max_v; G=new vector<edge3>[MAX_V]; level=new ll[MAX_V]; iter=new ll[MAX_V]; } */ void add_edge(ll from,ll to,ll cap){ G[from].push_back((edge3){to,cap,(ll)G[to].size()}); G[to].push_back((edge3){from,0,(ll)G[from].size()-1}); } void bfs(ll s){ memset(level,-1,sizeof(level)); queue<ll> que; level[s]=0; que.push(s); while(!que.empty()){ //cout<<que<<endl; ll v=que.front();que.pop(); //cout<<"v"<<v<<endl; //cout<<G[v]<<endl; for(ll i=0;i<(ll)G[v].size();i++){ edge3 &e=G[v][i]; if(e.cap>0 && level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } } } ll dfs(ll v,ll t,ll f){ if(v==t)return f; //cout<<"&i:"<<iter[v]<<" "<<G[v].size()<<endl; for(ll &i=iter[v];i<(ll)G[v].size();i++){ edge3 &e=G[v][i]; //cout<<e.cap<<" "<<level[v]<<" "<<level[e.to]<<endl; if(e.cap>0 && level[v]<level[e.to]){ ll d=dfs(e.to,t,my_min(f,e.cap)); //cout<<"d:"<<d<<endl; if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(ll s,ll t){ ll flow=0; for(;;){ bfs(s); //cout<<"bfs end\n"; if(level[t]<0)return flow; //cout<<level[t]<<endl; memset(iter,0,sizeof(iter)); ll f; while((f=dfs(s,t,INF))>0){ //cout<<f<<endl; flow+=f; } //cout<<f<<endl; } } //}; int main(){ time_t start=time(NULL); ll N,A,B; cin>>N; //Dinic F(200002); //Dinic F; //cout<<"INF:"<<F.INF<<endl; for(int i=0;i<N;i++){ //cerr<<i<<endl; cin>>A>>B; A--;B--; /* F.add_edge(200000,i,1); F.add_edge(i,100000+A,1); if(A!=B)F.add_edge(i,100000+B,1); F.add_edge(100000+i,200001,1); */ add_edge(200000,i,1); add_edge(i,100000+A,1); if(A!=B)add_edge(i,100000+B,1); add_edge(100000+i,200001,1); } //cerr<<"edge added\n"; //ll cnt=F.max_flow(200000,200001); ll cnt=max_flow(200000,200001); //cout<<cnt<<endl; if(cnt!=N){ cout<<"No\n"; return 0; } //ここから構築 cout<<"Yes\n"; cerr<<(double)time(NULL)-(double)start<<endl; return 0; }