제출 #415110

#제출 시각아이디문제언어결과실행 시간메모리
415110Kevin_Zhang_TWSimurgh (IOI17_simurgh)C++17
100 / 100
480 ms6628 KiB
#include <bits/stdc++.h> #include "simurgh.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 // My bug list : // integer overflow // 0based, 1based forgotten // index out of bound // n, m, i, j typo // some cases are missing int mqcnt; int qry(vector<int> r) { ++mqcnt; return count_common_roads(r); } const int MAX_N = 505; int id[MAX_N][MAX_N], state[MAX_N][MAX_N]; int dep[MAX_N], pa[MAX_N], n; bool vis[MAX_N], on_tree[MAX_N][MAX_N]; vector<pair<int,int>> te, alle; vector<int> tid; void dfs(int x, int lst) { pa[x] = lst; dep[x] = dep[lst] + 1; vis[x] = true; for (int i = 0;i < n;++i) if (!vis[i] && id[x][i] != -1) { dfs(i, x); te.pb(i, x); tid.pb(id[i][x]); on_tree[i][x] = on_tree[x][i] = true; } } pair<vector<int>, vector<int>> get_path(int a, int b) { vector<int> l, r; while (a != b) { if (dep[a] > dep[b]) { l.pb(a); a = pa[a]; } else { r.pb(b); b = pa[b]; } } return {l, r}; } vector<int> operator - (vector<int> a, int v) { assert(count(AI(a), v)); a.erase(find(AI(a), v)); return a; } vector<int> operator + (vector<int> a, int v) { a.pb(v); return a; } struct dsu { vector<int> g, sz; int F(int i) { return i == g[i] ? i : g[i] = F(g[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 g[b] = a, sz[a] += sz[b], true; } dsu(int n) { g.resize(n+10), sz.resize(n+10, 1); iota(AI(g), 0); } }; int get_cnt(vector<int> part) { vector<int> r = part; dsu D(n); for (int id : part) { auto [a, b] = alle[id]; D.M(a, b); } int sum = 0; for (auto [a, b] : te) if (D.M(a, b)) { r.pb(id[a][b]); sum += state[a][b]; } assert(r.size() == n-1); return qry(r) - sum; } void bs(vector<int> part, int sum) { if (sum == 0) return; if (part.size() == 1) { auto [a, b] = alle[ part[0] ]; state[a][b] = state[b][a] = 1; return; } int mid = part.size()/2; vector<int> l, r; for (int i = 0;i < part.size();++i) (i<mid?l:r).pb(part[i]); int cl = get_cnt(l); bs(l, cl); bs(r, sum-cl); } void solve(int h) { vector<int> cur; for (int i = 0;i < n;++i) if (id[h][i] != -1 && state[i][h] == -1) cur.pb(id[h][i]); if (cur.empty()) return; bs(cur, get_cnt(cur)); } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { int m = u.size(); ::n = n; for (int i = 0;i < n;++i) fill(id[i], id[i] + n, -1); for (int i = 0;i < m;++i) { int a = u[i], b = v[i]; alle.pb(a, b); id[a][b] = id[b][a] = i; state[a][b] = state[b][a] = -1; } dfs(0, 0); int tsum = qry(tid); for (int i = 0;i < m;++i) { auto [a, b] = alle[i]; if (on_tree[a][b]) continue; auto [l, r] = get_path(a, b); int cnt = 0; vector<int> not_sure, sure; for (int u : l) if (state[u][ pa[u] ] == -1) not_sure.pb(id[u][pa[u]]); else sure.pb(id[u][pa[u]]); for (int u : r) if (state[u][ pa[u] ] == -1) not_sure.pb(id[u][pa[u]]); else sure.pb(id[u][pa[u]]); if (not_sure.empty()) continue; vector<int> small, same, big; for (int eid : not_sure) { int qv = qry( (tid - eid) + id[a][b] ); if (qv > tsum) big.pb(eid); if (qv == tsum) same.pb(eid); if (qv < tsum) small.pb(eid); } int cur_v = -1; if (small.size()) cur_v = 0; if (big.size()) cur_v = 1; if (cur_v == -1 && same.size() == l.size() + r.size()) cur_v = 0; if (cur_v == -1 && sure.size()) { int qv = qry( (tid - sure[0]) + id[a][b] ); auto [x, y] = alle[ sure[0] ]; if (qv > tsum) cur_v = 1; if (qv == tsum) cur_v = state[x][y]; if (qv < tsum) cur_v = 0; } for (int eid : big) { auto [x, y] = alle[eid]; state[x][y] = state[y][x] = cur_v - 1; } for (int eid : small) { auto [x, y] = alle[eid]; state[x][y] = state[y][x] = cur_v + 1; } for (int eid : same) { auto [x, y] = alle[eid]; state[y][x] = state[x][y] = cur_v; } state[b][a] = state[a][b] = cur_v; } for (auto [a, b] : te) { if (state[a][b] == -1) state[a][b] = state[b][a] = 1; } assert(mqcnt <= n + n); for (int i = 0;i < n;++i) solve(i); vector<int> res; for (int i = 0;i < n;++i) for (int j = i+1;j < n;++j) { if (id[i][j] == -1) continue; if (state[i][j] == 1) res.pb(id[i][j]); DE(i, j, state[i][j]); } return res; }

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp: In function 'int get_cnt(std::vector<int>)':
simurgh.cpp:94:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  assert(r.size() == n-1);
      |         ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void bs(std::vector<int>, int)':
simurgh.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int i = 0;i < part.size();++i)
      |                 ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:142:7: warning: unused variable 'cnt' [-Wunused-variable]
  142 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:209:3: note: in expansion of macro 'DE'
  209 |   DE(i, j, state[i][j]);
      |   ^~
#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...