Submission #762224

#TimeUsernameProblemLanguageResultExecution timeMemory
762224minhcoolHighway Tolls (IOI18_highway)C++17
90 / 100
218 ms19372 KiB
//#define local #ifndef local #include "highway.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<ll, ll> ii; typedef pair<ii, ll> iii; typedef pair<ii, ii> iiii; const ll N = 3e5 + 5; const ll oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); ll rnd(ll l, ll r){ ll temp = rng() % (r - l + 1); return abs(temp) + l; } // ask(vector<ll>) vector<ii> Adj[N]; ll mini; ll n, m; vector<ii> v1, v2; bool vis[N]; bool ck = 0; vector<int> ok; int dist; /* void dfs(ll u, ll d){ vis[u] = 1; if(!ck) v1.pb({u, d}); else v2.pb({u, d}); // if(d == dist) ok.pb(u); for(auto it : Adj[u]){ if(it.se < (mini - 1)) continue; if(vis[it.fi]) continue; dfs(it.fi, d + 1); } }*/ bool cmp(ii a, ii b){ return a.se > b.se; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { n = N, m = U.size(); for(ll i = 0; i < m; i++){ Adj[U[i]].pb({V[i], i}); Adj[V[i]].pb({U[i], i}); } // first step: find the optimal ans by toggle all 0s ll opt; vector<int> temp; for(ll i = 0; i < m; i++) temp.pb(0); opt = ask(temp); // phase 1: let us set (1->i) to B in order to find a bridge + split graph llo two parts ll le = 0, ri = m - 1; while(le < ri){ ll mid = (le + ri) >> 1; temp.clear(); for(ll i = 0; i <= mid; i++) temp.pb(1); for(ll i = mid + 1; i < m; i++) temp.pb(0); ll get = ask(temp); if(get == opt) le = mid + 1; else ri = mid; } mini = le + 1; // phase 2: find S/T ck = 0; //dfs(U[le], 0); queue<int> q; vis[U[le]] = 1; q.push(U[le]); vector<int> distt(n + 1); while(!q.empty()){ int u = q.front(); q.pop(); // if(distt[u] == dist) ok.pb(u); v1.pb({u, distt[u]}); for(auto it : Adj[u]){ int v = it.fi; if(it.se < (mini - 1)) continue; if(!vis[v]){ vis[v] = 1; distt[v] = distt[u] + 1; q.push(v); } } } //ck = 1; //dfs(V[le], 0); sort(v1.begin(), v1.end(), cmp); //sort(v2.begin(), v2.end(), cmp); ll le2 = 0, ri2 = v1.size() - 1; while(le2 < ri2){ ll mid = (le2 + ri2) >> 1; temp.resize(m); for(ll i = 0; i < le; i++) temp[i] = 1; temp[le] = 0; for(ll i = le + 1; i < m; i++) temp[i] = 0; for(ll i = 0; i <= mid; i++){ ll u = v1[i].fi; for(auto it : Adj[u]){ if(it.se < mini) continue; temp[it.se] = 1; } } ll get = ask(temp); if(get == opt) le2 = mid + 1; else ri2 = mid; } /* ll le3 = 0, ri3 = v2.size() - 1; while(le3 < ri3){ ll mid = (le3 + ri3) >> 1; temp.resize(m); for(ll i = 0; i < le; i++) temp[i] = 1; temp[le] = 0; for(ll i = le + 1; i < m; i++) temp[i] = 0; for(ll i = 0; i <= mid; i++){ ll u = v2[i].fi; for(auto it : Adj[u]){ if(it.se < mini) continue; temp[it.se] = 1; } } ll get = ask(temp); if(get == opt) le3 = mid + 1; else ri3 = mid; }*/ int S = v1[(int)le2].fi; dist = opt / A; // cout << S << " " << opt << " " << A << " " << dist << "\n"; ok.clear(); mini = 0; for(int i = 0; i < n; i++) vis[i] = 0; for(int i = 0; i <= n; i++) distt[i] = 0; vis[S] = 1; q.push(S); while(!q.empty()){ int u = q.front(); q.pop(); if(distt[u] == dist) ok.pb(u); for(auto it : Adj[u]){ int v = it.fi; if(!vis[v]){ vis[v] = 1; distt[v] = distt[u] + 1; q.push(v); } } } /// dfs(S, 0); // for(auto it : ok) cout << it << " "; // cout << "\n"; assert(ok.size()); int le3 = 0, ri3 = ok.size() - 1; while(le3 < ri3){ int mid = (le3 + ri3) >> 1; temp.resize(m); for(int i = 0; i < m; i++) temp[i] = 0; for(int i = 0; i <= mid; i++){ int u = ok[i]; for(auto it : Adj[u]) temp[it.se] = 1; } ll get = ask(temp); if(get == opt) le3 = mid + 1; else ri3 = mid; } int T = ok[le3]; answer(S, T); //answer((int)v1[(int)le2].fi, (int)v2[(int)le3].fi); } #ifdef local void process(){ } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll t; cin >> t; while(t--) process(); } #endif
#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...