Submission #624155

#TimeUsernameProblemLanguageResultExecution timeMemory
624155Ronin13Highway Tolls (IOI18_highway)C++14
100 / 100
516 ms50512 KiB
#include "highway.h" #include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int NMAX = 1e6 + 1; vector <vector <int> > g(NMAX); int D[NMAX][2]; vector <int> p(NMAX, -1); int n; ll a, b; int d[NMAX][2]; ll sz1, sz2 = 0; map<pii, bool> used1; vector <bool> used(NMAX); void bfs(int x, int y){ queue <int> q; q.push(x); //cout << x << y; used1[{x, y}] = used1[{y, x}] = true; for(int i = 0; i < n; i++){ D[i][0] = D[i][1] = 1e9; d[i][0] = d[i][1] = -1; } D[x][0] = 0; q.push(x); while(!q.empty()){ int v = q.front(); // cout << v << ' '; q.pop(); for(int to : g[v]){ if(D[to][0] > D[v][0] + 1){ D[to][0] = D[v][0] + 1; q.push(to); } } } D[y][1] = 0; q.push(y); while(!q.empty()){ int v = q.front(); q.pop(); for(int to : g[v]){ if(D[to][1] > D[v][1] + 1){ D[to][1] = D[v][1] + 1; q.push(to); } } } q.push(x); int cnt = 1; d[x][0] = 0; while(!q.empty()){ int v = q.front(); q.pop(); for(int to : g[v]){ if(D[to][0] < D[to][1]){ if(d[to][0] == -1) {d[to][0] = cnt++, sz1++, used1[{v, to}] = used1[{to, v}] = true, q.push(to); } } } } q.push(y); cnt = 1; d[y][1] = 0; while(!q.empty()){ int v = q.front(); q.pop(); for(int to : g[v]){ if(D[to][1] <= D[to][0]){ if(d[to][1] == -1) d[to][1] = cnt++, sz2++, used1[{v, to}] = used1[{to, v}] = true, q.push(to); } } } } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { n = N; int m = U.size(); for(int i = 0; i < m; i++){ g[U[i]].pb(V[i]); g[V[i]].pb(U[i]); } ll a = A, b = B; vector <int> vec; vec.resize(m); const vector <int> v = vec; ll mn = ask(v); int l = -1, r = m; while(l + 1 < r){ int mid = (l + r) / 2; vector <int> xx; for(int i = 0; i < m; i++){ if(i <= mid) xx.pb(0); else xx.pb(1); } const vector <int> vv = xx; ll x = ask(vv); if(x == mn) r = mid; else l = mid; } // cout << r << "\n"; int x = U[r], y = V[r]; bfs(x, y); for(int i = 0; i < m; i++){ if(used1[{U[i], V[i]}]) used[i] = true; } l = -1, r = sz1 + 1; while(l + 1 < r){ int mid = (l + r) / 2; vector <int> xx; for(int i = 0; i < m; i++){ int u = U[i], v = V[i]; if(!used[i]) xx.pb(1); else{ if(d[u][0] <= mid && d[v][0] <= mid) xx.pb(0); else xx.pb(1); } } const vector <int> vv = xx; ll x = ask(vv); if(x == mn) r = mid; else l = mid; } int s; for(int i = 0; i < n; i++) if(d[i][0] == r) {s = i; break;} //cout << s << "\n"; l = -1, r = sz2; while(l + 1 < r){ int mid = (l + r) / 2; vector <int> xx; for(int i = 0; i < m; i++){ int u = U[i], v = V[i]; if(!used[i]) xx.pb(1); else{ if(d[u][1] <= mid && d[v][1] <= mid) xx.pb(0); else xx.pb(1); } } const vector <int> vv = xx; ll x = ask(vv); if(x == mn) r = mid; else l = mid; } //cout << r; int t; for(int i = 0; i < n; i++) if(d[i][1] == r) {t = i; break;} answer(s, t); }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:8: warning: unused variable 'a' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |        ^
highway.cpp:96:15: warning: unused variable 'b' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |               ^
highway.cpp:161:11: warning: 'second' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |     answer(s, t);
      |     ~~~~~~^~~~~~
highway.cpp:161:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...