Submission #1146972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146972		nickolasarapidis	Closing Time (IOI23_closing)	C++17	0 / 100	1129 ms	2162688 KiB

closing

#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;
        k++;
    }
    
    sort(dLevel2.begin(), dLevel2.end());
    
    k = 0;
    while(K - dLevel2[k].F >= 0){
        K -= dLevel2[k].F;
        levels[dLevel2[k].S] = 2;
        k++;
    }
    
    int ans = 0;
    for(int i = 0; i < N; i++){
        ans += levels[i];
    }
    
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17