oj.uz

Submission #847478

# Submission time Handle Problem Language Result Execution time Memory
847478 2023-09-09T17:35:09 Z nvmdava Closing Time (IOI23_closing) C++17
8 / 100
 159 ms 38596 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200'005;

vector<pair<int, ll> > adj[N];

ll dx[N];
int px[N];
int py[N];
ll dy[N];

ll d[N];
int p[N];


void dfs(int v, int par) {
    p[v] = par;
    for(auto& u : adj[v]) {
        if(u.first == par) continue;
        d[u.first] = u.second + d[v];
        dfs(u.first, v);
    }
}


int max_score(int n, int X, int Y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for(int i = 0; i < n; ++i){
        d[i] = dx[i] = dy[i] = p[i] = px[i] = py[i] = 0;
        adj[i].clear();
    }
    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]});
    }
    dfs(X, -1);
    swap(d, dx);
    swap(p, px);

    dfs(Y, -1);
    swap(d, dy);
    swap(p, py);

    int res = 0;

    vector<ll> dd;
    for(int i = 0; i < n; ++i) dd.push_back(min(dx[i], dy[i]));
    sort(dd.begin(), dd.end());
    ll tmp = k;
    for(int i = 0; i < n; ++i) {
        tmp -= dd[i];
        if(tmp >= 0) res = i + 1;
    }
    
    int cur = 0;
    dd.clear();
    for(int i = 0; i < n; ++i) {
        if(dx[i] + dy[i] == dx[Y]) {
            k -= min(dx[i], dy[i]);
            ++cur;
            if(k < 0) return res;
            dd.push_back(abs(dx[i] - dy[i]));
        }
    }

    sort(dd.begin(), dd.end());
    tmp = k;
    for(int i = 0; i < n; ++i) {
        tmp -= dd[i];
        if(tmp >= 0) res = i + 1 + cur;
    }

    return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 33740 KB Output is correct
2 Correct 114 ms 38596 KB Output is correct
3 Correct 159 ms 14672 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 3 ms 12124 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 3 ms 12124 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 3 ms 12124 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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