제출 #408112

#제출 시각아이디문제언어결과실행 시간메모리
408112Kevin_Zhang_TWSimurgh (IOI17_simurgh)C++17
0 / 100
421 ms12028 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 505, MAX_M = MAX_N * MAX_N; #include "simurgh.h" int qry(const vector<int> &r) { return count_common_roads(r); } struct dsu { vector<int> g, sz; dsu (int n) { g.resize(n+10), sz.resize(n+10, 1), iota(AI(g), 0); } int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); } int S(int i) { return sz[ F(i) ]; } bool M(int a, int b) { a = F(a), b = F(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); return sz[a] += sz[b], g[b] = a, true; } }; int id[MAX_N][MAX_N], m, n; bool isin[MAX_N][MAX_N], is1[MAX_N][MAX_N]; struct tree { vector<pair<int,int>> alle; vector<int> get_cycle(int a, int b) { vector<vector<int>> edge(n); for (auto [a, b] : alle) edge[a].pb(b), edge[b].pb(a); vector<int> res, stk; function<bool(int,int)> dfs = [&](int x, int lst) { stk.pb(x); if (x == b) { res = stk; return true; } for (int u : edge[x]) if (u != lst) { if (dfs(u, x)) return true; } stk.pop_back(); return false; }; dfs(a, a); return res; } void remove(int a, int b) { if (a > b) swap(a, b); alle.erase(find(AI(alle), make_pair(a, b))); } void add_edge(int a, int b) { if (a > b) swap(a, b); alle.pb(a, b); } }; vector<int> operator - (vector<int> a, int b) { a.erase(find(AI(a), b)); return a; } vector<int> to_id(vector<pair<int,int>> a) { vector<int> b; for (auto [x, y] : a) b.pb(id[x][y]); return b; } vector<int> operator + (vector<int> a, int b) { a.pb(b); return a; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { ::n = n; m = u.size(); vector<pair<int,int>> alle(m); for (int i = 0;i < m;++i) { id[v[i]][u[i]] = id[u[i]][v[i]] = i; alle[i] = {u[i], v[i]}; } // I need to find a tree vector<pair<int,int>> out, bad; tree T; { dsu D(n); for (auto [a, b] : alle) { if (D.M(a, b)) T.add_edge(a, b); else out.pb(a, b); } } dsu allz(n); auto upd = [&](int a, int b) { if (allz.M(a, b)) { bad.pb(a, b); isin[a][b] = isin[b][a] = true; } }; // then I want to find a forest which has all 0 for (auto [a, b] : out) { if (allz.F(a) == allz.F(b)) continue; auto cir = T.get_cycle(a, b); vector<int> tall; for (auto [x, y] : T.alle) tall.pb(id[x][y]); int old = qry(tall); for (int i = 1;i < cir.size();++i) { int x = cir[i-1], y = cir[i]; int val = qry(tall - id[x][y] + id[a][b]); if (val < old) break; if (val > old) { T.remove(x, y); T.add_edge(a, b); a = x, b = y; break; } } upd(a, b); } // then I need to put the bridges back to both ANS, and BAD dsu G(n); vector<int> ans; // cnt_bridges int cnt_b = n-1 - bad.size(); for (auto [a, b] : T.alle) if (allz.M(a, b)) { bad.pb(a, b); ans.pb(id[a][b]); isin[a][b] = isin[b][a] = true; G.M(a, b); is1[b][a] = is1[a][b] = true; } DE(cnt_b, qry(to_id(bad)), ans.size()); while (alle.size()) { DE(alle.size()); dsu D(n); vector<pair<int,int>> now; int sz = 0; for (auto [a, b] : alle) { if (!isin[a][b] && G.F(a) != G.F(b)) { if (D.M(a, b)) now.pb(a, b); else alle[sz++] = {a, b}; } } alle.resize(sz); int osz = now.size(), cnt_b = 0; DE(osz); for (auto [a, b] : bad) if (D.M(a, b)) { now.pb(a, b); cnt_b += is1[a][b]; } int val = qry(to_id(now)); if (val == cnt_b) continue; for (int i = cnt_b + 1;i <= val;++i) { int l = 0, r = n-cnt_b, m; while (l < r) { m = l + r >> 1; vector<pair<int,int>> q; dsu D(n); for (int j = 0;j <= m;++j) { D.M(now[j].first, now[j].second); q.pb(now[j]); } for (auto [a, b] : bad) if (D.M(a, b)) q.pb(a, b); if (qry(to_id(q)) >= i) r = m; else l = m+1; } auto [a, b] = now[l]; ans.pb(id[a][b]); DE(a, b); G.M(a, b); } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for (int i = 1;i < cir.size();++i) {
      |                  ~~^~~~~~~~~~~~
simurgh.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
simurgh.cpp:154:2: note: in expansion of macro 'DE'
  154 |  DE(cnt_b, qry(to_id(bad)), ans.size());
      |  ^~
simurgh.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
simurgh.cpp:158:3: note: in expansion of macro 'DE'
  158 |   DE(alle.size());
      |   ^~
simurgh.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
simurgh.cpp:171:3: note: in expansion of macro 'DE'
  171 |   DE(osz);
      |   ^~
simurgh.cpp:184:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  184 |     m = l + r >> 1;
      |         ~~^~~
simurgh.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
simurgh.cpp:202:3: note: in expansion of macro 'DE'
  202 |   DE(a, b);
      |   ^~
simurgh.cpp:170:7: warning: unused variable 'osz' [-Wunused-variable]
  170 |   int osz = now.size(), cnt_b = 0;
      |       ^~~
simurgh.cpp:143:6: warning: unused variable 'cnt_b' [-Wunused-variable]
  143 |  int cnt_b = n-1 - bad.size();
      |      ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...