Submission #870054

#	Time	Username	Problem	Language	Result	Execution time	Memory
870054		ThommyDB	Closing Time (IOI23_closing)	C++17	0 / 100	163 ms	29804 KiB

closing

#include<bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> adj;
vector<bool> visited;
vector<long long> distX, distY;

void dfs(int curr, long long d, vector<long long> &dist){
    visited[curr] = true;
    dist[curr] =d;
    for(pair<int, int> u : adj[curr]){
        if(!visited[u.first]){
            dfs(u.first, d+u.second, dist);
        }
    }
}

int solve(int N, long long K, int mx){
    int ans = 0;
    priority_queue<pair<int, int>> q;

    for(int i = 0; i < N; i++){
        q.push({min(distX[i], distY[i]), i});
    }
    vector<int> cnt(N, 0);
    while(!q.empty()){
        while(!q.empty() && (K < q.top().first || cnt[q.top().second] > mx-1)) q.pop();
        if(q.empty()) break;

        int t = q.top().first;
        int x = q.top().second;
        q.pop();
        ans++;
        cnt[x]++;
        K-=t;
        if(cnt[x]==1 && mx == 2){
            q.push({abs(distX[x] - distY[x]), x});
        }
    }
    if(K<0) return 0;
    else return ans;
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
    adj.assign(N, vector<pair<int, int>>(0));
    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]});
    }
    distX.resize(N, 0);
    distY.resize(N, 0);
    visited.assign(N, false);
    dfs(0, 0, distX);
    visited.assign(N, false);
    dfs(0, 0, distY);
    return max(solve(N, K, 1), solve(N, K, 2));
}

• 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