Submission #971392

#TimeUsernameProblemLanguageResultExecution timeMemory
971392vjudge1Prize (CEOI22_prize)C++17
0 / 100
1770 ms356332 KiB
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; struct tree { int n; vi par, niv, D; vector<vi> L, Anc; tree(int N) : n(N), L(N), par(N), niv(N) {} void add_edge(int u, int v) { L[u].push_back(v); L[v].push_back(u); } void set_dist(vi dist0) { D = dist0; } void init() { function<void(int, int, int)> dfs0 = [&](int u, int p, int li) { par[u] = p; niv[u] = li; for(auto it : L[u]) if(it != p) { dfs0(it, u, li + 1); } }; dfs0(0, -1, 0); Anc.push_back(par); for(int k = 1; (1 << k) <= n; ++k) { Anc.push_back(Anc.back()); for(int i = 0; i < n; ++i) Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]]; } } int lift(int u, int nr) { for(int i = 0; i < Anc.size(); ++i) if(nr & (1 << i)) u = Anc[i][u]; return u; } int lca(int u, int v) { if(niv[u] > niv[v]) swap(u, v); v = lift(v, niv[v] - niv[u]); if(u == v) return u; for(int i = int(Anc.size()) - 1; i >= 0; --i) if(Anc[i][u] != Anc[i][v]) { u = Anc[i][u]; v = Anc[i][v]; } return par[u]; } int dist(int u, int v) { int l = lca(u, v); return D[u] + D[v] - 2 * D[l]; } vi get_V(int k) { vi Re; function<void(int, int)> dfs = [&](int u, int p) { if(!k) return; Re.push_back(u); --k; for(auto it : L[u]) if(it != p) { dfs(it, u); } }; dfs(0, -1); return Re; } }; int main() { int n, k, q, t; cin >> n >> k >> q >> t; tree T1(n), T2(n); for(int i = 0; i < n; ++i) { int p; cin >> p; if(p != -1) T1.add_edge(i, p - 1); } for(int i = 0; i < n; ++i) { int p; cin >> p; if(p != -1) T2.add_edge(i, p - 1); } T1.init(); T2.init(); auto V = T1.get_V(k); for(auto it : V) cout << it + 1 << " "; cout << "\n"; vi dist(n, 0); for(int i = 1; i < V.size(); ++i) { cout << "? " << V[0] + 1 << " " << V[i] + 1 << endl; int a, b, c, d; cin >> a >> b >> c >> d; dist[V[i]] = a + b; } T1.set_dist(dist); for(int i = 0; i < q; ++i) { int a, b; cin >> a >> b; --a; --b; cout << T1.dist(a, b) << "\n"; } return 0; }

Compilation message (stderr)

Main.cpp: In constructor 'tree::tree(int)':
Main.cpp:11:16: warning: 'tree::L' will be initialized after [-Wreorder]
   11 |     vector<vi> L, Anc;
      |                ^
Main.cpp:10:8: warning:   'vi tree::par' [-Wreorder]
   10 |     vi par, niv, D;
      |        ^~~
Main.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     tree(int N) : n(N), L(N), par(N), niv(N) {}
      |     ^~~~
Main.cpp: In member function 'int tree::lift(int, int)':
Main.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0; i < Anc.size(); ++i)
      |                        ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1; i < V.size(); ++i) {
      |                    ~~^~~~~~~~~~
#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...