제출 #295131

#제출 시각아이디문제언어결과실행 시간메모리
295131Kastanda통행료 (IOI18_highway)C++11
90 / 100
988 ms13392 KiB
// M #include<bits/stdc++.h> #include "highway.h" #define pb push_back using namespace std; typedef long long ll; const int N = 90004, TOF = 32768; int n, m, ca, cb, dist, root, H[N]; ll MnCost; vector < int > alwaysMarked; vector < pair < int , int > > Adj[N]; inline ll Ask(vector < int > vec) { vector < int > TMp(m, 0); for (int i : vec) TMp[i] = 1; return ask(TMp); } inline bool HasImpact(vector < int > vec) { return (Ask(vec) > MnCost); } inline vector < int > MarkAll(vector < int > vec) { vector < int > TMp(m, 0), ret; for (int i : vec) for (auto e : Adj[i]) TMp[e.second] = 1; for (int i : alwaysMarked) for (auto e : Adj[i]) TMp[e.second] = 1; for (int i = 0; i < m; i ++) if (TMp[i]) ret.pb(i); return ret; } void find_pair(int _n, vector < int > _U, vector < int > _V, int _A, int _B) { n = _n; m = (int)_U.size(); for (int i = 0; i < m; i ++) { Adj[_U[i]].pb({_V[i], i}); Adj[_V[i]].pb({_U[i], i}); } ca = _A; cb = _B; MnCost = Ask(vector < int > {}); dist = MnCost / ca; auto GenerateVec = [](int l, int r){ vector < int > vec; for (int i = l; i < r; i ++) vec.pb(i); return vec; }; int le = 0, ri = n, md; if (n > TOF * 2 && HasImpact(MarkAll(GenerateVec(0, TOF)))) le = 0, ri = TOF; else if (n > TOF * 2) alwaysMarked = GenerateVec(0, TOF), le = TOF, ri = n; while (ri - le > 1) { md = (le + ri) >> 1; if (HasImpact(MarkAll(GenerateVec(0, md)))) ri = md; else le = md; } alwaysMarked = GenerateVec(0, le); root = le; queue < int > qu; memset(H, -1, sizeof(H)); H[root] = 0; qu.push(root); while (qu.size()) { int v = qu.front(); qu.pop(); for (auto u : Adj[v]) if (u.first >= le && H[u.first] == -1) H[u.first] = H[v] + 1, qu.push(u.first); } vector < int > Rs; vector < int > marked(n, 0); for (int i : alwaysMarked) marked[i] = 1; for (int w = 0; w < 2; w ++) { vector < int > srt; for (int i = 0; i < n; i ++) if (marked[i] == 0) srt.pb(i); sort(srt.begin(), srt.end(), [&](int i, int j){return H[i] > H[j];}); auto GenVec = [&](int l, int r){ assert(r <= (int)srt.size()); vector < int > vec; for (int i = l; i < r; i ++) vec.pb(srt[i]); return vec; }; le = 0, ri = (int)srt.size(); if (srt.size() > TOF * 2 && HasImpact(MarkAll(GenVec(0, TOF)))) le = 0, ri = TOF; else if (srt.size() > TOF * 2) { for (int i = 0; i < TOF; i ++) alwaysMarked.pb(srt[i]); le = TOF; } while (ri - le > 1) { md = (le + ri) >> 1; if (HasImpact(MarkAll(GenVec(0, md)))) ri = md; else le = md; } Rs.pb(srt[le]); qu.push(srt[le]); marked[srt[le]] = 1; while (qu.size()) { int v = qu.front(); qu.pop(); for (auto u : Adj[v]) if (!marked[u.first] && u.first != root && H[u.first] == H[v] - 1) marked[u.first] = 1, qu.push(u.first); } } assert((int)Rs.size() == 2); answer(Rs[0], Rs[1]); return ; }
#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...