oj.uz

Submission #842500

# Submission time Handle Problem Language Result Execution time Memory
842500 2023-09-03T01:33:01 Z cjoa Closing Time (IOI23_closing) C++17
8 / 100
 111 ms 33940 KB 
#include "closing.h"

#include <vector>
#include <algorithm>
#include <queue>

#include <iostream>

using namespace std;

using llong = long long;

const llong INF = 4e18;

struct Edge {
    int u, v, w;
    int opp(int x) const {
        return x == u ? v : u;
    }
};

vector<Edge> edges;
vector< vector<int> > tree;

llong K;
void dfs(int u, int p, llong t, vector<llong>& closing_times) {
    if (t > K)
        return;
    closing_times[u] = t;
    for (int eid : tree[u]) {
        int v = edges[eid].opp(u);
        if (v == p) continue;
        int w = edges[eid].w;
        dfs(v, u, t + w, closing_times);
    }
}

int dfs2(int u, int p, llong t, vector<llong>& closing_times) {
    if (t > closing_times[u])
        return 0;
    int res = 1;
    for (int eid : tree[u]) {
        int v = edges[eid].opp(u);
        if (v == p) continue;
        int w = edges[eid].w;
        res += dfs2(v, u, t + w, closing_times);
    }
    return res;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    ::K = K;
//  cerr << "K: " << K << endl;

    tree = vector< vector<int> >(N);
    for (int j = 0; j < N-1; j++) {
        int u = U[j], v = V[j], w = W[j];
        int eid = edges.size();
        edges.push_back({u, v, w});
        tree[u].push_back(eid);
        tree[v].push_back(eid);
    }

    // subtask1

    vector<llong> closing_timesX(N, INF);
    dfs(X, -1, 0, closing_timesX);

    vector<llong> closing_timesY(N, INF);
    dfs(Y, -1, 0, closing_timesY);

    priority_queue< tuple<llong,int,int> > pq;
    llong sum = 0;
    for (int u = 0; u < N; ++u) {
        llong mx = max(closing_timesX[u], closing_timesY[u]);
        llong mn = min(closing_timesX[u], closing_timesY[u]);
    //    cerr << "u: " << u << "  mn: " << mn << "  mx: " << mx << endl;
        if (mn > K) continue;
        if (mx <= K) {
           pq.emplace(mx - mn, 2, u);
           sum += mx;
        }
        else {
           pq.emplace(mn, 1, u);
           sum += mn;
        }
    }
//    cerr << "sum: " << sum << endl;

    while (sum > K) {
        auto [dif, cnt, u] = pq.top(); pq.pop();
    //    cerr << "u=" << u << "  dif=" << dif << "  cnt=" << cnt << endl;
        sum -= dif;
        if (cnt == 2) {
           pq.emplace(min(closing_timesX[u], closing_timesY[u]), 1, u);
        }
    }

    vector<llong> closing_times(N, 0);
    while (!pq.empty()) {
        auto [dif, cnt, u] = pq.top(); pq.pop();
        if (cnt == 2)
           closing_times[u] = max(closing_timesX[u], closing_timesY[u]);
        else if (cnt == 1)
           closing_times[u] = min(closing_timesX[u], closing_timesY[u]);
    }

    int res = dfs2(X, -1, 0, closing_times) +
              dfs2(Y, -1, 0, closing_times);
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 26520 KB Output is correct
2 Correct 111 ms 33940 KB Output is correct
3 Correct 69 ms 7112 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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