Submission #1146971

#TimeUsernameProblemLanguageResultExecution timeMemory
1146971nickolasarapidisClosing Time (IOI23_closing)C++17
0 / 100
1097 ms27968 KiB
#include <bits/stdc++.h> #include "closing.h" using namespace std; #define ll long long #define F first #define S second vector<pair<int, int>> adj[200000]; vector<int> dX(200000), dY(200000); void dfs(int s, int e, char c){ for(auto u : adj[s]){ int a = u.first, w = u.second; if(a == e) continue; if(c == 'X') dX[a] = dX[s] + w; else dY[a] = dY[s] + w; dfs(a, s, c); } } int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){ for(int i = 0; i < N - 1; i++){ adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } dX[X] = 0; dY[Y] = 0; dfs(X, -1, 'X'); dfs(Y, -1, 'Y'); vector<pair<int, int>> dLevel1(N), dLevel2(N); vector<int> levels(N, 0); for(int i = 0; i < N; i++){ dLevel1[i].F = min(dX[i], dY[i]); dLevel2[i].F = abs(max(dX[i], dY[i]) - dLevel1[i].F); dLevel1[i].S = dLevel2[i].S = i; } sort(dLevel1.begin(), dLevel1.end()); int k = 0; while(K - dLevel1[k].F >= 0){ K -= dLevel1[k].F; levels[dLevel1[k].S] = 1; } sort(dLevel2.begin(), dLevel2.end()); k = 0; while(K - dLevel2[k].F >= 0){ K -= dLevel2[k].F; levels[dLevel2[k].S] = 2; } int ans = 0; for(int i = 0; i < N; i++){ ans += levels[i]; } return ans; }
#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...