제출 #435444

#제출 시각아이디문제언어결과실행 시간메모리
435444benedict0724통행료 (IOI18_highway)C++17
51 / 100
361 ms9952 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, int N) { for(int i=0;i<N;i++) visited[i] = false; 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 = bfsorder[l]; else T = bfsorder[l]; return; } int mid = (l + r)/2; makezero(); for(int i=l;i<=mid;i++) { for(auto u : adj[bfsorder[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, N); w.resize(M); makezero(); ll zerotoll = ask(w); binarysearch(0, N-1, zerotoll); now = N; bfs(S, N); binarysearch(0, N-2, zerotoll); answer(S, T); }

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:29:30: warning: unused variable 'j' [-Wunused-variable]
   29 |             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...