結果
問題 | No.1640 簡単な色塗り |
ユーザー |
![]() |
提出日時 | 2021-06-17 01:00:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,761 bytes |
コンパイル時間 | 1,287 ms |
コンパイル使用メモリ | 99,188 KB |
実行使用メモリ | 59,628 KB |
最終ジャッジ日時 | 2023-09-12 01:31:45 |
合計ジャッジ時間 | 37,359 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,624 KB |
testcase_01 | AC | 3 ms
4,420 KB |
testcase_02 | AC | 3 ms
4,468 KB |
testcase_03 | AC | 2 ms
4,524 KB |
testcase_04 | AC | 242 ms
44,624 KB |
testcase_05 | AC | 266 ms
59,052 KB |
testcase_06 | AC | 2 ms
4,416 KB |
testcase_07 | AC | 3 ms
4,568 KB |
testcase_08 | AC | 2 ms
4,632 KB |
testcase_09 | AC | 3 ms
4,628 KB |
testcase_10 | AC | 344 ms
34,752 KB |
testcase_11 | AC | 252 ms
30,328 KB |
testcase_12 | AC | 216 ms
27,176 KB |
testcase_13 | AC | 562 ms
53,088 KB |
testcase_14 | AC | 552 ms
53,144 KB |
testcase_15 | AC | 145 ms
20,496 KB |
testcase_16 | AC | 186 ms
24,772 KB |
testcase_17 | AC | 441 ms
44,892 KB |
testcase_18 | AC | 25 ms
8,608 KB |
testcase_19 | AC | 201 ms
27,132 KB |
testcase_20 | AC | 308 ms
33,876 KB |
testcase_21 | AC | 244 ms
28,968 KB |
testcase_22 | AC | 18 ms
7,104 KB |
testcase_23 | AC | 344 ms
36,032 KB |
testcase_24 | AC | 74 ms
13,752 KB |
testcase_25 | AC | 230 ms
27,620 KB |
testcase_26 | AC | 439 ms
42,620 KB |
testcase_27 | AC | 145 ms
19,796 KB |
testcase_28 | AC | 608 ms
50,148 KB |
testcase_29 | AC | 410 ms
42,352 KB |
testcase_30 | AC | 71 ms
13,296 KB |
testcase_31 | AC | 1,251 ms
58,180 KB |
testcase_32 | AC | 1,785 ms
53,744 KB |
testcase_33 | AC | 1,368 ms
37,316 KB |
testcase_34 | AC | 1,321 ms
46,208 KB |
testcase_35 | AC | 935 ms
39,496 KB |
testcase_36 | AC | 70 ms
12,960 KB |
testcase_37 | AC | 124 ms
16,704 KB |
testcase_38 | AC | 1,228 ms
54,188 KB |
testcase_39 | AC | 357 ms
27,228 KB |
testcase_40 | AC | 375 ms
27,388 KB |
testcase_41 | AC | 1,443 ms
48,680 KB |
testcase_42 | AC | 535 ms
32,256 KB |
testcase_43 | AC | 557 ms
30,288 KB |
testcase_44 | AC | 483 ms
32,108 KB |
testcase_45 | AC | 303 ms
26,724 KB |
testcase_46 | AC | 90 ms
14,844 KB |
testcase_47 | AC | 44 ms
11,128 KB |
testcase_48 | AC | 1,640 ms
54,956 KB |
testcase_49 | AC | 16 ms
7,420 KB |
testcase_50 | AC | 3 ms
4,412 KB |
testcase_51 | AC | 2 ms
4,536 KB |
testcase_52 | WA | - |
testcase_53 | WA | - |
07_evil_01.txt | AC | 1,815 ms
112,088 KB |
07_evil_02.txt | WA | - |
ソースコード
#include <algorithm> #include <atcoder/internal_queue> #include <cassert> #include <limits> #include <queue> #include <vector> #include <time.h> #include <chrono> #include <sys/time.h> #include <iostream> #include <fstream> using namespace std; using namespace atcoder; #define ll long long #define INF 1000000 using std::cout; using std::endl; using std::chrono::duration_cast; using std::chrono::milliseconds; using std::chrono::seconds; using std::chrono::system_clock; //namespace atcoder { ostream& operator<<(ostream& os,vector<int>& a){ for(int i:a){ os<<i<<" "; } return os<<"\n"; } vector<ll> ans(200010,-1); struct _edge { ll to, rev; ll cap; ll index; }; template <class Cap> struct mf_graph { public: mf_graph() : _n(0) {} mf_graph(ll n) : _n(n), g(n) {} ll add_edge(ll from, ll to, Cap cap,ll index) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); ll m = (long long)pos.size(); pos.push_back({from, (long long)g[from].size()}); ll from_id = (long long)g[from].size(); ll to_id = (long long)g[to].size(); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap, index}); g[to].push_back(_edge{from, from_id, 0, index}); return m; } struct edge { ll from, to; Cap cap, flow; }; edge get_edge(ll i) { ll m = (long long)pos.size(); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } Cap flow(ll s, ll t) { return flow(s, t, std::numeric_limits<Cap>::max()); } Cap flow(ll s, ll t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); time_t flow_start=time(NULL); std::vector<ll> level(_n), iter(_n); internal::simple_queue<ll> que; cerr<<level.size()<<endl; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { ll v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; if (time(NULL)-flow_start>1.8){ cout<<"No\n"; exit(0); } Cap res = 0; //cerr<<"size:"<<level.size()<<endl; ll level_v = level[v]; for (long long& i = iter[v]; i < (long long)g[v].size(); i++) { //cout<<"i:"<<i<<endl; _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; // if(e.index!=-1){ // ans[e.index] = e.to+1; // cout<<"ans update"<<endl; // } // cout<<"v:"<<v<<" "<<i<<endl; // cout<<e.to<<" "<<e.rev<<" "<<e.cap<<" "<<e.index<<endl<<endl; res += d; if (res == up) break; } return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); //cout<<level<<endl; if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); while (flow < flow_limit) { Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } } return flow; } //private: ll _n; std::vector<std::pair<ll, ll>> pos; std::vector<std::vector<_edge>> g; }; ostream& operator<<(ostream& os,const _edge& a){ return os<<a.to<<" "<<a.rev<<" "<<a.cap<<" "<<a.index; } //} // namespace atcoder signed main(){ //ifstream ifs("input.txt"); auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count(); ll N,A,B; cin>>N; //ifs>>N; //Dinic F(200002); //Dinic F; //cout<<"INF:"<<F.INF<<endl; mf_graph<ll> F(2*N+2); for(ll i=0;i<N;i++){ //cerr<<i<<endl; cin>>A>>B; //ifs>>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); */ F.add_edge(2*N,i,1,-1); F.add_edge(i,N+A,1,i); if(A!=B)F.add_edge(i,N+B,1,i); F.add_edge(N+i,2*N+1,1,-1); } //cerr<<"edge added\n"; //ll cnt=F.max_flow(200000,200001); ll cnt=F.flow(2*N,2*N+1); //cout<<cnt<<endl; if(cnt!=N){ cout<<"No\n"; return 0; } //ここから構築 cout<<"Yes\n"; /* for(int i=0;i<N;i++){ cout<<ans[i]<<endl; } */ for(ll i=N;i<2*N;i++){ ll s=F.g.at(i).size(); //cout<<i<<endl; for(ll j=0;j<s;j++){ if(F.g.at(i).at(j).cap!=0){ ans.at(F.g.at(i).at(j).to)=i-N+1; } //cout<<F.g.at(i).at(j)<<endl; } //cout<<endl; //cout<<ans.at(i)<<endl; } for(ll i=0;i<N;i++){ cout<<ans.at(i)<<endl; } auto end= duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count(); cerr<<end-start<<endl; return 0; }