Submission #957405

#TimeUsernameProblemLanguageResultExecution timeMemory
957405LukapPrize (CEOI22_prize)C++14
0 / 100
2558 ms402804 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 500; const int LOG = 21; int n, k, q, t; int rod[2][MAXN][LOG], d[2][MAXN], dt[2][MAXN], tim, bio[2][MAXN], rj[2][MAXN]; vector<int> djeca[2][MAXN], v; vector<pair<int, int> > susjedi[2][MAXN]; void dfs (int x, int br, int g) { d[g][x] = br; dt[g][x] = tim++; for (auto nx: djeca[g][x]) dfs (nx, br + 1, g); } bool cmp (int x, int y) { return dt[1][x] < dt[1][y]; } int lca (int g, int x, int y) { if (d[g][x] > d[g][y]) swap (x, y); for (int i = LOG - 1; i >= 0; i--) { if (d[g][rod[g][y][i]] >= d[g][x]) y = rod[g][y][i]; } for (int i = LOG - 1; i >= 0; i--) { if (rod[g][x][i] != rod[g][y][i]) { x = rod[g][x][i]; y = rod[g][y][i]; } } if (x != y) x = rod[g][x][0]; return x; } void dfs2 (int x, int g) { bio[g][x] = 0; for (auto it: susjedi[g][x]) { int nx = it.first; if (bio[g][nx] != -1) continue; rj[g][nx] = rj[g][x] + it.second; dfs2 (nx, g); } } int main () { memset (bio, -1, sizeof (bio)); cin >> n >> k >> q >> t; for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) { int a; cin >> a; if (a == -1) rod[i][j][0] = j; else { a--; rod[i][j][0] = a; djeca[i][a].push_back (j); } } } for (int i = 0; i < 2; i++) { for (int j = 1; j < LOG; j++) { for (int l = 0; l < n; l++) rod[i][l][j] = rod[i][rod[i][l][j - 1]][j - 1]; } } for (int i = 0; i < n; i++) { if (rod[0][i][0] == i) { tim = 0; dfs (i, 0, 0); } if (rod[1][i][0] == i) { tim = 0; dfs (i, 0, 1); } } for (int i = 0; i < n; i++) { if (dt[0][i] < k) v.push_back (i); } sort (v.begin (), v.end (), cmp); for (auto it: v) cout << it + 1 << ' '; cout << endl; for (int i = 0; i < k - 1; i++) cout << "? " << v[i] + 1 << ' ' << v[i + 1] + 1 << endl; cout << '!' << endl; for (int i = 0; i < k - 1; i++) { int a, b, c, d; cin >> a >> b >> c >> d; int x = v[i], y = v[i + 1]; int lca0 = lca (0, x, y), lca1 = lca (1, x, y); susjedi[0][lca0].push_back ({x, a}); susjedi[0][x].push_back ({lca0, -a}); susjedi[0][lca0].push_back ({y, b}); susjedi[0][y].push_back ({lca0, -b}); susjedi[1][lca1].push_back ({x, c}); susjedi[1][x].push_back ({lca1, -c}); susjedi[1][lca1].push_back ({y, d}); susjedi[1][y].push_back ({lca1, -d}); } return 0; dfs2 (v[0], 0); dfs2 (v[0], 1); for (int i = 0; i < t; i++) { int a, b; cin >> a >> b; a--;b--; int lca0 = lca (0, a, b), lca1 = lca (1, a, b); cout << rj[0][a] + rj[0][b] - 2 * rj[0][lca0] << ' ' << rj[1][a] + rj[1][b] - 2 * rj[1][lca1] << endl; } return 0; }
#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...