Submission #1226178

#TimeUsernameProblemLanguageResultExecution timeMemory
1226178adam17Prize (CEOI22_prize)C++20
0 / 100
822 ms216232 KiB
#include <iostream> #include <vector> using namespace std; int N, K, Q, T, koren, _, H; vector<int> rodice; vector<vector<int>> synove; vector<int> mnozina; vector<bool> mnozina_b; vector<int> vahy; vector<int> hladiny; vector<int> vzdalenost; vector<vector<int>> skocky; void vytvor_mnozinu(int v) { if (mnozina.size() < K) { mnozina.push_back(v); } for (int s:synove[v]) { hladiny[s] = hladiny[v] + 1; vytvor_mnozinu(s); } } void pocitej_vzdalenost(int v) { for (int s: synove[v]) if (mnozina_b[s]) { vzdalenost[s] = vzdalenost[v] + vahy[s]; // cout << "vzdalenost[" << s << "] = " << vzdalenost[s] << endl; pocitej_vzdalenost(s); } } int hledej_vidlicku(int a, int b, int h) { // cout << "Hledej_vidlicku(" << a << ", " << b << ", " << h << ");\n"; if (h == -1) { return a; } else { int a_ = ((skocky[h][a] == -1) ? -1 : (skocky[h][rodice[skocky[h][a]]])); int b_ = ((skocky[h][b] == -1) ? -1 : (skocky[h][rodice[skocky[h][b]]])); if (a_ == b_) { return hledej_vidlicku(a, b, h - 1); } else { return hledej_vidlicku(a_, b_, h - 1); } } } int vidlicka(int a, int b) { if (hladiny[b] > hladiny[a]) { return vidlicka(b, a); } int hh = 1, h = 0; while (hladiny[a] != hladiny[b]) { if ((hladiny[a] - hladiny[b]) % (2 * hh) != 0) { a = skocky[h][a]; } h++; hh *= 2; } return hledej_vidlicku(a, b, H - 2); } int main() { cin >> N >> K >> Q >> T; rodice.resize(N); for (int i = 0; i < N; i++) { cin >> rodice[i]; if (rodice[i] == -1) { koren = i; } else { rodice[i]--; } } for (int i = 0; i < N; i++) { cin >> _; } synove.resize(N); for (int i = 0; i < N; i++) { synove[i].resize(0); } for (int i = 0; i < N; i++) if (i != koren) { synove[rodice[i]].push_back(i); } hladiny.resize(N); hladiny[koren] = 0; vytvor_mnozinu(koren); for (int i = 0; i < K; i++) { cout << mnozina[i] + 1 << ((i != K - 1) ? ' ' : '\n'); } for (int i = 1; i < K; i++) { cout << "? " << rodice[mnozina[i]] + 1 << ' ' << mnozina[i] + 1 << endl; } cout << "!\n"; flush(cout); cout.flush(); vahy.resize(N); for (int i = 1; i < K; i++) { cin >> _ >> _ >> _ >> _; vahy[mnozina[i]] = _; } H = 1; int hh = 1; while (hh < N - 1) { H++; hh *= 2; } skocky.resize(H); skocky[0].resize(N); for (int i = 0; i < N; i++) { skocky[0][i] = rodice[i]; } for (int h = 1; h < H; h++) { skocky[h].resize(N); for (int i = 0; i < N; i++) { skocky[h][i] = ((skocky[h - 1][i] == -1) ? -1 : (skocky[h - 1][skocky[h - 1][i]])); } } mnozina_b.resize(N); for (int i = 0; i < N; i++) { mnozina_b[i] = false; } for (int x: mnozina) { mnozina_b[x] = true; } vzdalenost.resize(N); vzdalenost[koren] = 0; pocitej_vzdalenost(koren); for (int t = 0; t < T; t++) { int a, b; cin >> a >> b; a--; b--; int c = vidlicka(a, b); // cout << "vidlicka(" << a << ", " << b << ") = " << c << endl; cout << vzdalenost[a] + vzdalenost[b] - 2 * vzdalenost[c] << ' ' << vzdalenost[a] + vzdalenost[b] - 2 * vzdalenost[c] << 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...