제출 #614157

#제출 시각아이디문제언어결과실행 시간메모리
614157fvogel499통행료 (IOI18_highway)C++17
51 / 100
216 ms36552 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define int long long #define vi vector<int> #define pii pair<int, int> #define f first #define s second #define sz(x) (int)((x).size()) const int siz = 1e6+40; int nbE; vi graph [siz]; int dist [2][siz]; int bounceOn [siz]; int caller(vector<int> where) { vector<signed> u(nbE, 0); for (int i : where) { u[i] = 1; // se heavy } int r = ask(u); return r; } void bfs(const int t, int src) { queue<int> q; q.push(src); dist[t][src] = 0; while (!q.empty()) { int x = q.front(); q.pop(); for (int y : graph[x]) { if (dist[t][y] == -1) { dist[t][y] = dist[t][x] + 1; q.push(y); } } } } int whoIncrease(vi edgeSet, int refD) { while (sz(edgeSet) != 1) { assert(!edgeSet.empty()); vi leftSet, rightSet; for (int i : edgeSet) { if (sz(leftSet) <= sz(rightSet)) { leftSet.push_back(i); } else { rightSet.push_back(i); } } int loc = caller(leftSet); assert(loc >= refD); if (loc > refD) { edgeSet = leftSet; } else { edgeSet = rightSet; } } return edgeSet[0]; } void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) { for (int i = 0; i < n; i++) graph[i].clear(); nbE = sz(edgeX); int distVert = caller({}); vi allEdges; for (int i = 0; i < nbE; i++) { allEdges.push_back(i); } const int magicEdge = whoIncrease(allEdges, distVert); for (int i = 0; i < nbE; i++) { graph[edgeX[i]].push_back(edgeY[i]); graph[edgeY[i]].push_back(edgeX[i]); } for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -1; bfs(0, edgeX[magicEdge]); bfs(1, edgeY[magicEdge]); for (int i = 0; i < n; i++) { assert(dist[0][i] != -1 && dist[1][i] != -1); if (dist[0][i] < dist[1][i]) { dist[1][i] = -1; } else { dist[0][i] = -1; } } for (int i = 0; i < n; i++) bounceOn[i] = -1; for (int t = 0; t < 2; t++) { for (int i = 0; i < nbE; i++) if (i != magicEdge) { if (dist[t][edgeX[i]] == -1 || dist[t][edgeY[i]] == -1) continue; if (dist[t][edgeX[i]] > dist[t][edgeY[i]]) { bounceOn[edgeX[i]] = i; } else { bounceOn[edgeY[i]] = i; } } } vi between; for (int i = 0; i < nbE; i++) if (i != magicEdge) { if ((dist[0][edgeX[i]] == -1) != (dist[0][edgeY[i]] == -1)) { between.push_back(i); } } vi res; for (int t = 0; t < 2; t++) { vector<pair<int, int>> cand; for (int i = 0; i < n; i++) if (dist[t][i] != -1) { if (bounceOn[i] != -1) { cand.push_back({min(dist[t][edgeX[bounceOn[i]]], dist[t][edgeY[bounceOn[i]]]), bounceOn[i]}); } } sort(cand.begin(), cand.end()); int bs = -1; for (int i = (1<<20); i; i /= 2) { int prop = bs+i; if (prop > sz(cand)) continue; vi where; for (int j = prop; j < sz(cand); j++) { where.push_back(cand[j].s); } for (int j : between) { where.push_back(j); } int loc = caller(where); if (loc > distVert) { bs = prop; } } if (bs == -1 || bs == sz(cand)) { if (t == 0) { res.push_back(edgeX[magicEdge]); } else { res.push_back(edgeY[magicEdge]); } continue; } int loc; if (dist[t][edgeX[cand[bs].second]] > dist[t][edgeY[cand[bs].second]]) { loc = edgeX[cand[bs].second]; } else { loc = edgeY[cand[bs].second]; } res.push_back(loc); } answer(res[0], res[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...
#Verdict Execution timeMemoryGrader output
Fetching results...