제출 #727493

#제출 시각아이디문제언어결과실행 시간메모리
727493bitaro1337Prize (CEOI22_prize)C++14
0 / 100
2436 ms437760 KiB
//BITARO BITARO BITARO #include <bits/stdc++.h> using namespace std; const int K = 20, N = 1e6 + 5; int jump[2][N][K], depth[2][N], time_in[2][N], dist[2][N], vis[2][N], tt[2], root[2]; vector<int> g[2][N]; vector<pair<int, int>> adj[2][N]; void dfs(int t, int u) { time_in[t][u] = tt[t]++; for(int j = 1; j < K; ++j) { jump[t][u][j] = jump[t][jump[t][u][j - 1]][j - 1]; } for(int v: g[t][u]) { jump[t][v][0] = u; depth[t][v] = depth[t][u] + 1; dfs(t, v); } } void get_distances(int t, int u) { vis[t][u] = 1; for(auto x: adj[t][u]) { int v = x.first, w = x.second; if(vis[t][v]) continue; dist[t][v] = dist[t][u] + w; get_distances(t, v); } } int lca(int t, int a, int b) { if(depth[t][a] < depth[t][b]) swap(a, b); for(int j = K - 1; j >= 0; --j) { if(jump[t][a][j] && depth[t][jump[t][a][j]] >= depth[t][b]) { a = jump[t][a][j]; } } if(a == b) return a; for(int j = K - 1; j >= 0; --j) { if(jump[t][a][j] && jump[t][b][j] && jump[t][a][j] != jump[t][b][j]) { a = jump[t][a][j]; b = jump[t][b][j]; } } return jump[t][a][0]; } int main() { int n, k, q, T; cin >> n >> k >> q >> T; for(int t = 0; t < 2; ++t) { for(int i = 1; i <= n; ++i) { int p; cin >> p; if(p == -1) root[t] = i; else g[t][p].push_back(i); } dfs(t, root[t]); } vector<int> nodes(n); iota(nodes.begin(), nodes.end(), 1); sort(nodes.begin(), nodes.end(), [&](int i, int j){return time_in[0][i] < time_in[0][j];}); while(nodes.size() > k) nodes.pop_back(); if(time_in[0][root[1]] >= k) { nodes.pop_back(); nodes.push_back(root[1]); } sort(nodes.begin(), nodes.end(), [&](int i, int j){return time_in[1][i] < time_in[1][j];}); for(int x: nodes) cout << x + 1 << " "; cout << "\n"; cout.flush(); for(int i = 0; i + 1 < k; ++i) cout << "? " << nodes[i] << " " << nodes[i + 1] << "\n"; cout << "!\n"; cout.flush(); for(int i = 0; i + 1 < k; ++i) { for(int t = 0; t < 2; ++t) { int u = nodes[i], v = nodes[i + 1]; int l = lca(t, u, v); int c1, c2; cin >> c1 >> c2; adj[t][l].push_back({u, c1}); adj[t][u].push_back({l, -c1}); adj[t][l].push_back({v, c2}); adj[t][v].push_back({l, -c2}); } } get_distances(0, root[0]); get_distances(1, root[1]); vector<pair<int, int>> Q(T); for(int i = 0; i < T; ++i) { cin >> Q[i].first >> Q[i].second; } for(int i = 0; i < T; ++i) { int u = Q[i].first, v = Q[i].second; for(int t = 0; t < 2; ++t) { cout << dist[t][u] + dist[t][v] - 2 * dist[t][lca(t, u, v)] << " "; } cout << "\n"; } cout.flush(); }

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

Main.cpp: In function 'int main()':
Main.cpp:56:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     while(nodes.size() > k) nodes.pop_back();
      |           ~~~~~~~~~~~~~^~~
#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...