Submission #435412

#TimeUsernameProblemLanguageResultExecution timeMemory
435412benedict0724Highway Tolls (IOI18_highway)C++17
0 / 100
29 ms2996 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<int, int>> adj[90002]; vector<int> w; int now, M; int bfsorder[90002]; bool visited[90002]; int S = -1, T = -1; void bfs(int x) { visited[x] = true; queue<int> q; q.push(x); while(!q.empty()) { int curr = q.front(); q.pop(); bfsorder[--now] = curr; for(auto u : adj[curr]) { int i = u.first, j = u.second; if(!visited[i]) { visited[i] = true; q.push(i); } } } } void makezero() { for(int i=0;i<M;i++) w[i] = 0; } void binarysearch(int l, int r, ll zerotoll) { if(l == r) { if(S == -1) S = l; else T = l; return; } int mid = (l + r)/2; makezero(); for(int i=l;i<=mid;i++) { for(auto u : adj[i]) { w[u.second] = 1; } } ll toll = ask(w); if(toll > zerotoll) binarysearch(l, mid, zerotoll); else binarysearch(mid+1, r, zerotoll); } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { M = U.size(); for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); } now = N; bfs(0); w.resize(M); ll zerotoll = ask(w); binarysearch(0, N-1, zerotoll); now = N; bfs(S); binarysearch(0, N-1, zerotoll); answer(S, T); }

Compilation message (stderr)

highway.cpp: In function 'void bfs(int)':
highway.cpp:28:30: warning: unused variable 'j' [-Wunused-variable]
   28 |             int i = u.first, j = u.second;
      |                              ^
#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...