제출 #255334

#제출 시각아이디문제언어결과실행 시간메모리
255334Erkhemkhuu통행료 (IOI18_highway)C++17
51 / 100
261 ms19192 KiB
#include <bits/stdc++.h> #include <highway.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define F first #define S second const int N = 150005; pair <int, int> par[N]; vector <int> w; vector < pair <int, int> > adj[N]; int flat[N], timer; void dfs(int v, int p) { flat[timer++] = v; for(auto &u: adj[v]) { if(u.F == p) continue; par[u.F] = {v, u.S}; dfs(u.F, v); } return; } void find_pair(int n, vector <int> u, vector <int> v, int a, int b) { int i, m, l, r, mid, s, t; ll max_cost; m = u.size(); w.resize(m); for(i = 0; i < m; i++) { adj[u[i]].pb({v[i], i}); adj[v[i]].pb({u[i], i}); } dfs(0, -1); w.assign(m, 1); max_cost = ask(w); w.assign(m, 0); l = 1; r = n - 1; while(l + 1 < r) { mid = (l + r) / 2; for(i = l; i <= mid; i++) w[par[flat[i]].S] = 1; if(ask(w) < max_cost) l = mid; else { r = mid; for(i = l; i <= mid; i++) w[par[flat[i]].S] = 0; } } s = flat[l + 1]; w.assign(m, 0); timer = 0; memset(flat, 0, sizeof(flat)); memset(par, 0, sizeof(par)); dfs(s, -1); l = 1; r = n - 1; while(l + 1 < r) { mid = (l + r) / 2; for(i = l; i <= mid; i++) w[par[flat[i]].S] = 1; if(ask(w) < max_cost) l = mid; else { r = mid; for(i = l; i <= mid; i++) w[par[flat[i]].S] = 0; } } t = flat[l + 1]; assert(s >= 0 && s < n && t >= 0 && t < n); answer(s, t); 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...