結果
問題 | No.1640 簡単な色塗り |
ユーザー | harurun |
提出日時 | 2021-06-16 21:47:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,907 bytes |
コンパイル時間 | 1,150 ms |
コンパイル使用メモリ | 94,848 KB |
実行使用メモリ | 46,836 KB |
最終ジャッジ日時 | 2023-09-12 01:34:55 |
合計ジャッジ時間 | 15,521 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
8,776 KB |
testcase_01 | AC | 2 ms
4,504 KB |
testcase_02 | AC | 3 ms
4,504 KB |
testcase_03 | AC | 3 ms
4,708 KB |
testcase_04 | AC | 222 ms
27,692 KB |
testcase_05 | AC | 241 ms
34,604 KB |
testcase_06 | AC | 3 ms
4,392 KB |
testcase_07 | AC | 3 ms
4,508 KB |
testcase_08 | AC | 2 ms
4,396 KB |
testcase_09 | AC | 3 ms
4,464 KB |
testcase_10 | AC | 280 ms
22,092 KB |
testcase_11 | AC | 204 ms
19,100 KB |
testcase_12 | AC | 178 ms
17,552 KB |
testcase_13 | AC | 478 ms
32,600 KB |
testcase_14 | AC | 444 ms
31,580 KB |
testcase_15 | AC | 118 ms
13,740 KB |
testcase_16 | AC | 150 ms
16,208 KB |
testcase_17 | AC | 367 ms
27,748 KB |
testcase_18 | AC | 23 ms
6,840 KB |
testcase_19 | AC | 170 ms
17,332 KB |
testcase_20 | AC | 236 ms
21,508 KB |
testcase_21 | AC | 197 ms
18,744 KB |
testcase_22 | AC | 16 ms
6,132 KB |
testcase_23 | AC | 260 ms
22,748 KB |
testcase_24 | AC | 60 ms
9,888 KB |
testcase_25 | AC | 168 ms
17,788 KB |
testcase_26 | AC | 313 ms
25,504 KB |
testcase_27 | AC | 110 ms
13,368 KB |
testcase_28 | AC | 433 ms
30,656 KB |
testcase_29 | AC | 322 ms
26,044 KB |
testcase_30 | AC | 56 ms
9,760 KB |
testcase_31 | TLE | - |
testcase_32 | AC | 1,391 ms
33,288 KB |
testcase_33 | AC | 631 ms
24,096 KB |
testcase_34 | AC | 994 ms
30,556 KB |
testcase_35 | AC | 575 ms
25,664 KB |
testcase_36 | AC | 55 ms
9,580 KB |
testcase_37 | AC | 88 ms
11,796 KB |
testcase_38 | TLE | - |
testcase_39 | AC | 247 ms
17,484 KB |
testcase_40 | AC | 259 ms
17,792 KB |
testcase_41 | AC | 921 ms
30,976 KB |
testcase_42 | AC | 326 ms
21,272 KB |
testcase_43 | AC | 349 ms
22,656 KB |
testcase_44 | AC | 322 ms
21,108 KB |
testcase_45 | AC | 208 ms
18,272 KB |
testcase_46 | AC | 67 ms
11,220 KB |
testcase_47 | AC | 35 ms
8,472 KB |
testcase_48 | AC | 1,649 ms
35,916 KB |
testcase_49 | AC | 13 ms
6,620 KB |
testcase_50 | AC | 2 ms
4,408 KB |
testcase_51 | AC | 3 ms
4,404 KB |
testcase_52 | TLE | - |
testcase_53 | TLE | - |
07_evil_01.txt | AC | 1,421 ms
67,636 KB |
07_evil_02.txt | TLE | - |
ソースコード
#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> using namespace std; using namespace atcoder; #define ll long long #define INF 1000000000000000000 //namespace atcoder { vector<ll> ans(200010,-1); struct _edge { int to, rev; ll cap; }; template <class Cap> struct mf_graph { public: mf_graph() : _n(0) {} mf_graph(int n) : _n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = int(pos.size()); pos.push_back({from, int(g[from].size())}); int from_id = int(g[from].size()); int to_id = int(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = int(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(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector<int> level(_n), iter(_n); internal::simple_queue<int> que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int 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; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < int(g[v].size()); i++) { _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; res += d; if (res == up) break; } return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); 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; } int _n; std::vector<std::pair<int, int>> pos; std::vector<std::vector<_edge>> g; }; //} // namespace atcoder int main(){ ll N,A,B; cin>>N; mf_graph<ll> F(2*N+2); for(int i=0;i<N;i++){ cin>>A>>B; A--;B--; F.add_edge(2*N,i,1); F.add_edge(i,N+A,1); if(A!=B)F.add_edge(i,N+B,1); F.add_edge(N+i,2*N+1,1); } ll cnt=F.flow(2*N,2*N+1); if(cnt!=N){ cout<<"No\n"; return 0; } cout<<"Yes\n"; for(int i=N;i<2*N;i++){ ll s=F.g.at(i).size(); for(int 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; } } } for(int i=0;i<N;i++){ cout<<ans.at(i)<<endl; } return 0; }