제출 #611768

#제출 시각아이디문제언어결과실행 시간메모리
611768Jomnoi통행료 (IOI18_highway)C++17
12 / 100
142 ms9064 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; // subtask 1, 2 const int MAX_N = 9e4 + 5; int S, T; long long result; vector <int> U, V, W; vector <int> graph[MAX_N]; vector <int> canbeanswer; int holdedge[MAX_N]; void dfs(int u, int p, int depth) { if(depth == 0) { canbeanswer.push_back(u); return; } for(auto i : graph[u]) { int v = u ^ U[i] ^ V[i]; if(v != p) { holdedge[v] = i; dfs(v, u, depth - 1); } } } void dfs2(int u, int p) { canbeanswer.push_back(u); for(auto i : graph[u]) { int v = u ^ U[i] ^ V[i]; if(v != p) { holdedge[v] = i; dfs2(v, u); } } } void find_pair(int N, vector <int> u, vector <int> v, int A, int B) { int M = u.size(); U.resize(M); V.resize(M); W.resize(M, 0); bool sub3 = true; for(int i = 0; i < M; i++) { U[i] = u[i], V[i] = v[i]; graph[U[i]].push_back(i); graph[V[i]].push_back(i); if(U[i] != i or V[i] != i + 1) { sub3 = false; } } if(sub3 == true) { int rt; for(int i = 0; i < N; i++) { if(graph[i].size() == 1) { rt = i; } } dfs2(rt, -1); W.resize(M, 1); long long need = ask(W); int l = 1, r = N - 1; while(l <= r) { int mid = (l + r) / 2; W.clear(); W.resize(M, 0); for(int i = 1; i <= mid; i++) { W[holdedge[canbeanswer[i]]] = 1; } result = ask(W); if(result < need) { l = mid + 1; } else { r = mid - 1; S = mid; } } l = 1, r = S - 1; while(l <= r) { int mid = (l + r) / 2; W.clear(); W.resize(M, 0); for(int i = mid; i <= S; i++) { W[holdedge[canbeanswer[i]]] = 1; } result = ask(W); if(result < need) { r = mid - 1; } else { l = mid + 1; T = mid; } } answer(canbeanswer[S], canbeanswer[T]); } else { // sub12 S = 0; result = ask(W); int numberofEdge = result / A; dfs(0, -1, numberofEdge); int l = 0, r = canbeanswer.size() - 1; while(l <= r) { int mid = (l + r) / 2; W.clear(); W.resize(M, 0); for(int i = 0; i <= mid; i++) { W[holdedge[canbeanswer[i]]] = 1; } result = ask(W); if(result == 1ll*numberofEdge * A) { l = mid + 1; } else { r = mid - 1; T = mid; } } answer(S, canbeanswer[T]); } }

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:13: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         dfs2(rt, -1);
      |         ~~~~^~~~~~~~
#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...