Submission #1082036

#TimeUsernameProblemLanguageResultExecution timeMemory
1082036LaMatematica14Closing Time (IOI23_closing)C++17
8 / 100
122 ms44872 KiB
#include <bits/stdc++.h> using namespace std; struct tree { vector<vector<array<long long, 2>>> adj; void dfs(int ba, vector<long long> &dist, vector<int> &p) { for (auto x : adj[ba]) { if (x[0] == p[ba]) continue; dist[x[0]] = dist[ba]+x[1]; p[x[0]] = ba; dfs(x[0], dist, p); } } int m(int N, int X, int Y, long long K, vector<int> &U, vector<int> &V, vector<int> &W) { vector<long long> dx(N, 0); vector<long long> dy(N, 0); vector<int> px(N, -1); vector<int> py(N, -1); adj.resize(N); for (long long i = 0; i < N-1; i++ ) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } dfs(X, dx, px); dfs(Y, dy, py); vector<int> acx(N, 0); vector<int> acy(N, 0); // ho gia' comprato la x,y vector<int> rex(N, 0); vector<int> rey(N, 0); // priority_queue<array<long long, 3>> d; for (long long i = 0; i < N; i++) { if (i == X) { acx[X] = 1; rex[X] = 1; for (auto x : adj[X]) { if (x[0] == px[X]) continue; rex[x[0]] = 1; } } else if (i == Y) { acy[Y] = 1; rey[Y] = 1; for (auto x : adj[Y]) { if (x[0] == py[Y]) continue; rey[x[0]] = 1; } } else if (dx[i] < dy[i]) d.push({-dx[i], i, 0}); else d.push({-dy[i], i, 1}); } vector<int> done(N, 0); long long att = 0, k = 2; while (k < 2*N && att-d.top()[0] <= K) { att -= d.top()[0]; k++; auto a = d.top(); d.pop(); if (a[2]) { acy[a[1]] = 1; if (!done[a[1]] && rex[a[1]] == 1) { done[a[1]] =1 ; d.push({-abs(dx[a[1]]-dy[a[1]]), a[1], 0}); } for (auto x : adj[a[1]]) { if (x[0] == py[a[1]]) continue; rey[x[0]] = 1; if (!done[x[0]] && acx[x[0]] == 1) { done[x[0]] = 1; d.push({-abs(dx[x[0]]-dy[x[0]]), x[0], 1}); } } } else { acx[a[1]] = 1; if (!done[a[1]] && rey[a[1]] == 1) { done[a[1]] = 1; d.push({-abs(dx[a[1]]-dy[a[1]]), a[1], 1}); } for (auto x : adj[a[1]]) { if (x[0] == px[a[1]]) continue; rex[x[0]] = 1; if (!done[x[0]] && acy[x[0]] == 1) { done[x[0]] = 1; d.push({-abs(dx[x[0]]-dy[x[0]]), x[0], 0}); } } } if (a[1] == -1) continue; } return k; } }; int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W) { tree a; return a.m(N, X, Y, K, U, V, W); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...