oj.uz

Submission #870054

# Submission time Handle Problem Language Result Execution time Memory
870054 2023-11-06T19:22:33 Z ThommyDB Closing Time (IOI23_closing) C++17
0 / 100
 163 ms 29804 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 29804 KB 1st lines differ - on the 1st token, expected: '451', found: '183930'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -