제출 #1041503

#제출 시각아이디문제언어결과실행 시간메모리
1041503yanb통행료 (IOI18_highway)C++14
18 / 100
185 ms262144 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; #define int long long #define pii pair<long long, long long> void dfs(int v, vector<vector<pii>> &g, vector<int> &p, vector<int> &e, vector<bool> &leaf) { for (auto [u, eu] : g[v]) { if (u != p[v]) { p[u] = v; e[u] = eu; leaf[v] = 0; dfs(u, g, p, e, leaf); } } } int find_one(int n, vector<signed> U, vector<signed> V, int A, int B, int S) { vector<int> p(n, -1), e(n, -1); vector<bool> leaf(n, 1); vector<vector<pii>> g(n); for (int i = 0; i < n - 1; i++) { g[U[i]].push_back({V[i], i}); g[V[i]].push_back({U[i], i}); } dfs(S, g, p, e, leaf); int k = 0; vector<int> leaves; for (int i = 0; i < n; i++) { if (leaf[i]) { leaves.push_back(i); //cout << i << " "; k++; } } //cout << "\n"; vector<signed> w(n - 1); int zero = ask(w); int dist = zero / A; int l = -1, r = k; while (r - l > 1) { int md = (l + r) / 2; vector<signed> w(n - 1); for (int i = 0; i < md; i++) { int v = leaves[i]; while (p[v] != -1 && !w[e[v]]) { w[e[v]] = 1; v = p[v]; } } if (ask(w) != dist * B) l = md; else r = md; } //cout << r << "\n"; int v = leaves[l], vdist = 0; while (p[v] != -1) { v = p[v]; vdist++; } int ll = 0, rr = vdist + 1; while (rr - ll > 1) { int md = (ll + rr) / 2; vector<signed> w(n - 1); int v = leaves[l]; for (int i = 0; i < md; i++) { w[e[v]] = 1; v = p[v]; } if (ask(w) == zero) ll = md; else rr = md; } v = leaves[l]; for (int i = 0; i < ll; i++) { v = p[v]; } return v; } void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) { int u = find_one(n, U, V, A, B, 0); int v = find_one(n, U, V, A, B, u); answer(u, v); }

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

highway.cpp: In function 'void dfs(long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&, std::vector<bool>&)':
highway.cpp:10:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |  for (auto [u, eu] : g[v]) {
      |            ^
#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...