제출 #891674

#제출 시각아이디문제언어결과실행 시간메모리
891674vjudge1통행료 (IOI18_highway)C++17
51 / 100
203 ms262144 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; vector<ii> E; struct tree { int n; vi par, par_cent, sz; vector<vi> L, G; tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {} void add_edge(int u, int v) { L[u].push_back(v); L[v].push_back(u); } void init() { vi on(n, 1); function<void(int, int)> dfs_sz = [&](int u, int p) { sz[u] = 1; for(auto it : L[u]) { if(on[it] && it != p) { dfs_sz(it, u); sz[u] += sz[it]; } } }; function<int(int, int, int)> find_c = [&](int u, int p, int slim) { for(auto it : L[u]) if(on[it] && it != p && 2 * sz[it] > slim) return find_c(it, u, slim); return u; }; function<void(int, int) > dfs_cent = [&](int u, int pc) { dfs_sz(u, -1); int c = find_c(u, -1, sz[u]); on[c] = 0; par_cent[c] = pc; if(pc != -1) { G[pc].push_back(c); } for(auto it : L[c]) if(on[it]) dfs_cent(it, c); }; dfs_cent(0, -1); } void solve() { function<void(int, int, vi&)> dfs_comp = [&](int u, int p, vi& V) { V.push_back(u); for(auto it : G[u]) dfs_comp(it, u, V); }; int cost_baza = ask(vi(E.size(), 0)); auto dif = [&](int u, vector<vi>& Fii, int st, int dr) { set<int> S = {u}; for(int i = st; i <= dr; ++i) for(auto it : Fii[i]) S.insert(it); vi w; for(auto [u, v] : E) { if(S.count(u) + S.count(v)) w.push_back(1); else w.push_back(0); } return ask(w) - cost_baza; }; vi capete; function<void(int, int, int)> dfs_solve = [&](int c, int pc, int nr) { vector<vi> comp_fii; for(auto it : G[c]) { comp_fii.push_back(vi()); dfs_comp(it, c, comp_fii.back()); } int pst = -1, pdr = comp_fii.size(), nrfii = comp_fii.size(); int v = dif(c, comp_fii, 0, nrfii - 1); if(!v) { if(nr == 1) { // v e unul dintre s & t capete.push_back(v); return; } else { ///uhhh, wtf? assert(0); } } for(int step = 31 - __builtin_clz(nrfii); step >= 0; --step) { if(pst + (1 << step) < nrfii) { if(!dif(c, comp_fii, 0, pst + (1 << step))) pst += (1 << step); } if(pdr - (1 << step) >= 0) { if(!dif(c, comp_fii, pdr - (1 << step), nrfii - 1)) pdr -= (1 << step); } } ++pst; --pdr; }; assert(capete.size() == 2); } int cine(int rad) { vi niv(n); function<void(int, int, int)> dfs = [&](int u, int p, int li) { niv[u] = li; for(auto it : L[u]) { if(it != p) { dfs(it, u, li + 1); } } }; vi re; for(int i = 0; i < n; ++i) { re.push_back(i); } dfs(rad, -1, 0); sort(re.begin(), re.end(), [&](int a, int b) { return niv[a] < niv[b]; }); int st = 0, dr = n - 1, mij; int q0 = 0; auto query = [&](int p) { static vi used(n, 0); for(int i = 0; i < n; ++i) used[i] = 0; for(int i = 0; i <= p; ++i) used[re[i]] = 1; vi w; for(auto [u, v] : E) { if(used[u] && used[v]) w.push_back(1); else w.push_back(0); } int v = ask(w) - q0; return v + q0; }; q0 = query(dr); int cm = query(dr); while(st < dr) { mij = (st + dr) / 2; if(query(mij) == q0) { dr = mij; } else st = mij + 1; } return re[st]; } }; void find_pair(int N, vi U, vi V, int A, int B) { tree T(N); for(int i = 0; i < U.size(); ++i) { T.add_edge(U[i], V[i]); E.push_back({U[i], V[i]}); } T.init(); int s = T.cine(0); int t = T.cine(s); answer(s, t); }

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

highway.cpp: In constructor 'tree::tree(int)':
highway.cpp:13:16: warning: 'tree::L' will be initialized after [-Wreorder]
   13 |     vector<vi> L, G;
      |                ^
highway.cpp:12:8: warning:   'vi tree::par' [-Wreorder]
   12 |     vi par, par_cent, sz;
      |        ^~~
highway.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}
      |     ^~~~
highway.cpp: In member function 'int tree::cine(int)':
highway.cpp:144:13: warning: unused variable 'cm' [-Wunused-variable]
  144 |         int cm = query(dr);
      |             ^~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0; i < U.size(); ++i) {
      |                    ~~^~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...