제출 #274843

#제출 시각아이디문제언어결과실행 시간메모리
274843junseoSimurgh (IOI17_simurgh)C++17
100 / 100
388 ms9580 KiB
#include "simurgh.h" #include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define all(v) (v).begin(), (v).end() #define rmin(r, x) r = min(r, x); #define rmax(r, x) r = max(r, x); #define ends ' ' #define endl '\n' #define fastio ios_base::sync_with_stdio(0), cin.tie(0) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 505; const int maxm = maxn * maxn; int n, m, K; pii pa[maxn]; bool visited[maxn], used[maxm]; int gold[maxm], k[maxm], h[maxn]; vector<pii> edge, adj[maxn], ch[maxn], bk[maxn], rbk[maxn]; vector<int> dfs_tree; int count_common_roads(const vector<int>& r); int count_k(vector<int> v, vector<pii> rep) { vector<int> q; for(auto [add, sub] : rep) q.eb(add); int i = 0, j = 0; while(i < v.size()) { if(j < rep.size() && v[i] == rep[j].se) { ++i; ++j; continue; } q.eb(v[i++]); } return count_common_roads(q); } void dfs(int u, int p) { visited[u] = true; for(auto [v, i] : adj[u]) if(v != p && !used[i]) { used[i] = true; if(visited[v]) { bk[u].eb(i, ch[v].back().se); rbk[v].eb(u, i); continue; } dfs_tree.eb(i); ch[u].eb(v, i); pa[v] = {u, i}; h[v] = h[u] + 1; dfs(v, u); } } void solve_tree(int u) { sort(all(rbk[u]), [&](pii a, pii b) { return h[a.fi] > h[b.fi]; }); for(auto [v, i] : rbk[u]) { vector<int> tedge; bool all = true, no = true; while(v != u) { tedge.eb(pa[v].se); if(gold[tedge.back()] != -1) all = false; else no = false; v = pa[v].fi; } if(no) continue; if(all) { int nk = n, xk = 0; for(auto j : tedge) { vector<pii> dum; dum.eb(i, j); k[j] = count_k(dfs_tree, dum); rmin(nk, k[j]); rmax(xk, k[j]); } if(nk != xk) { gold[i] = nk - (K - 1); for(auto j : tedge) gold[j] = (nk == k[j]); } else { if(nk == K - 1) { for(auto j : tedge) gold[j] = true; gold[i] = false; } else for(auto j : tedge) gold[j] = false; } } else { for(auto j : tedge) if(gold[j] != -1) { vector<pii> dum; dum.eb(i, j); gold[i] = count_k(dfs_tree, dum) - K + gold[j]; break; } for(auto j : tedge) if(gold[j] == -1) { vector<pii> dum; dum.eb(i, j); gold[j] = K + gold[i] - count_k(dfs_tree, dum); } } } for(auto [v, i] : ch[u]) solve_tree(v); } void solve_back(vector<pii> e, int l, int r, int cnt) { // count_k = K - S(gold[sub]) + S(gold[add]) // S(gold[add]) = count_k - K + S(gold[sub]) if(l > r) return; if(cnt == 0) { for(auto [add, sub] : e) gold[add] = false; return; } if(cnt == r - l + 1) { for(auto [add, sub] : e) gold[add] = true; return; } int mid = l + r >> 1; vector<pii> t; for(int i = mid + 1; i <= r; ++i) { t.eb(e.back()); e.pop_back(); } reverse(all(t)); int ret = count_k(dfs_tree, e) - K; for(auto [add, sub] : e) ret += gold[sub]; solve_back(e, l, mid, ret); solve_back(t, mid + 1, r, cnt - ret); } std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) { n = _n, m = u.size(); for(int i = 0; i < m; ++i) { edge.eb(u[i], v[i]); adj[u[i]].eb(v[i], i); adj[v[i]].eb(u[i], i); } dfs(0, -1); sort(all(dfs_tree)); K = count_k(dfs_tree, vector<pii>()); memset(gold, -1, sizeof(gold)); solve_tree(0); for(int i = 0; i < n; ++i) if(!bk[i].empty()) { sort(all(bk[i]), [](pii a, pii b) { return a.se < b.se; }); vector<pii> v; for(auto t : bk[i]) if(gold[t.fi] == -1) v.eb(t); if(!v.empty()) { int cnt = count_k(dfs_tree, v) - K; for(auto [add, sub] : v) cnt += gold[sub]; solve_back(v, 0, v.size() - 1, cnt); } } vector<int> ans; for(int i = 0; i < m; ++i) if(gold[i]) ans.eb(i); return ans; }

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

simurgh.cpp: In function 'int count_k(std::vector<int>, std::vector<std::pair<int, int> >)':
simurgh.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while(i < v.size()) {
      |        ~~^~~~~~~~~~
simurgh.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(j < rep.size() && v[i] == rep[j].se) {
      |      ~~^~~~~~~~~~~~
simurgh.cpp: In function 'void solve_back(std::vector<std::pair<int, int> >, int, int, int)':
simurgh.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |  int mid = l + r >> 1;
      |            ~~^~~
#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...