제출 #1112338

#제출 시각아이디문제언어결과실행 시간메모리
1112338thelegendary08Highway Tolls (IOI18_highway)C++17
5 / 100
104 ms9140 KiB
#include "highway.h" #include<bits/stdc++.h> #define vi vector<int> #define vb vector<bool> #define vpii vector<pair<int,int>> #define pb push_back #define vvi vector<vector<int>> #define ll long long int #define f0r(i,n) for(int i = 0; i<n; i++) #define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n'; using namespace std; void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { int m = U.size(); ll ret; vi w(m,0); ret = ask(w); int base = ret; int len = ret/A; vi dep(N); dep[0] = 0; queue<int>q; q.push(0); vb vis(N); vis[0] = 1; vpii adj[N]; f0r(i, m){ adj[U[i]].pb({V[i], i}); adj[V[i]].pb({U[i], i}); } vi par(N, -1); while(!q.empty()){ int cur = q.front(); q.pop(); for(auto u : adj[cur]){ if(vis[u.first])continue; par[u.first] = u.second; vis[u.first] = 1; dep[u.first] = dep[cur] + 1; q.push(u.first); } } //vout(par); vi poss; f0r(i, N){ if(dep[i] == len)poss.pb(i); } //vout(poss); int l = 0; int r = poss.size() - 1; while(l < r){ vi w(m, 0); int mid = (l + r)/2; //set l to mid for(int i = l; i<=mid; i++){ w[par[poss[i]]] = 1; } ret = ask(w); if(ret > base){ r = mid; } else{ l = mid + 1; } } answer(0, poss[l]); }
#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...