제출 #255341

#제출 시각아이디문제언어결과실행 시간메모리
255341Erkhemkhuu통행료 (IOI18_highway)C++17
5 / 100
266 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 < 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 run(int l, int r, int type) { for(int i = l; i <= r; i++) w[par[flat[i]].S] = type; return; } int go(int l, int r, int max_cost) { while(l + 1 < r) { int mid = (l + r) / 2; run(l, mid, 1); if(ask(w) < max_cost) l = mid; else { r = mid; run(l, mid, 0); } } return l + 1; } void find_pair(int n, vector <int> u, vector <int> v, int a, int b) { int i, m, 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); s = flat[go(1, n - 1, max_cost)]; w.assign(m, 0); timer = 0; memset(flat, 0, sizeof(flat)); dfs(s, -1); t = flat[go(1, n - 1, max_cost)]; 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...