Submission #1198464

#TimeUsernameProblemLanguageResultExecution timeMemory
1198464ozner77통행료 (IOI18_highway)C++20
0 / 100
10 ms3564 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define ll long long vector<vector<ll>> adj; map<ll,map<ll,ll>> M; vector<ll> depth,parent; vector<vector<ll>> prof; vector<int> w; ll n; void dfs(ll cur, ll prev) { prof[depth[cur]].push_back(cur); parent[cur]=prev; for (ll v:adj[cur]) { if (v!=prev){ depth[v]=depth[cur]+1; dfs(v, cur); } } } /*int ask(int w[]){ return 1; } void answer(ll x,ll y){ cout<<x; }*/ ll chance(ll cur){ ll l,r,m; l=0; vector<ll> hijos; for (auto x:adj[cur]) { if (x!= parent[cur]) { hijos.push_back(x); } } r=hijos.size(); while(l<r){ m=(l+r)/2; for(ll i=0;i<=m;i++){ w[M[cur][hijos[i]]]=0; } for(ll i=m+1;i<hijos.size();i++){ w[M[cur][hijos[i]]]=1; } ll ans1=ask(w); for(ll i=0;i<=m;i++){ w[M[cur][hijos[i]]]=1; } for(ll i=m+1;i<hijos.size();i++){ w[M[cur][hijos[i]]]=0; } ll ans2=ask(w); if(ans1==ans2){ return -1; }else if(ans1<ans2){ l=m+1; }else{ r=m; } } return hijos[l]; } void find_pair(int N,vector<int> U,vector<int> V, int A, int B){ adj.resize(N); prof.resize(N); depth.resize(N); w.resize(N); n=N; for(ll i=0;i<N;i++){ w[i]=0; } for(int i=0;i<N-1;i++){ adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); M[U[i]][V[i]]=i; M[V[i]][U[i]]=i; } ll xd=ask(w); ll a=xd/A; depth[0]=0; dfs(0, -1); ll b=a-1; for(auto x:prof[b]){ ll ans=chance(x); if(ans!=-1){ answer(0,ans); } } }
#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...