oj.uz

Submission #1081977

# Submission time Handle Problem Language Result Execution time Memory
1081977 2024-08-30T13:43:09 Z LaMatematica14 Closing Time (IOI23_closing) C++17
8 / 100
 1000 ms 368452 KB 
#include <bits/stdc++.h>
using namespace std; 

struct tree {
    vector<vector<array<int, 2>>> adj;
    void dfs(int ba, vector<long long> &dist, vector<int> &p) {
        for (auto x : adj[ba]) {
            if (x[0] == p[ba]) continue;
            dist[x[0]] = dist[ba]+x[1];
            p[x[0]] = ba;
            dfs(x[0], dist, p);
        }
    }
    queue<int> agg(long long a, vector<int> &re, vector<int> &p) {
        queue<int> t;
        re[a] = 1;
        if (re[p[a]] < 2) return t;
        stack<int> upd; upd.push(a);
        while (!upd.empty()) {
            int n = upd.top(); upd.pop();
            re[n] = 2; t.push(n);
            for (auto x : adj[n]) {
                if (x[0] == p[a]) continue;
                if (re[x[0]] == 0) continue;
                upd.push(x[0]);
            }
        }
        return t;
    }

    int m(int N, int X, int Y, long long K, vector<int> &U, vector<int> &V, vector<int> &W) {
        vector<long long> dx(N, 1e16);
        vector<long long> dy(N, 1e16);
        vector<int> px(N, -1);
        vector<int> py(N, -1);
        adj.resize(N);
        for (long long 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, dx, px);
        dfs(Y, dy, py);

        vector<int> ax(N, 0); vector<int> ay(N, 0); //0 spento, 1 acc, 2 reachable
        priority_queue<array<long long, 3>> d;
        for (long long i = 0; i < N; i++) {
            if (i == X) {
                d.push({-dy[X], X, 1});
                ax[X] = 2;
            }
            else if (i == Y) {
                d.push({-dx[Y], Y, 0});
                ay[Y] = 2;
            }
            else if (dx[i] < dy[i]) d.push({-dx[i], i, 1});
            else d.push({-dy[i], i, 0});
        }

        long long att = 0, k = 2;
        while (k < 2*N && att-d.top()[0] <= K) {
            att -= d.top()[0]; k++;
            auto a = d.top(); d.pop();
            if (a[1] < 0) continue;
            if (a[2]) {
                queue<int> r = agg(a[1], ay, py);
                while (!r.empty()) {
                    d.push({dx[r.front()]-dy[r.front()], -1, 0});
                    r.pop();
                }
            }
            else {
                queue<int> r = agg(a[1], ax, px);
                while (!r.empty()) {
                    d.push({dy[r.front()]-dx[r.front()], -1, 0});
                    r.pop();
                }
            }
        }
        return k;

    }

};

int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W) {
    tree a;
    return a.m(N, X, Y, K, U, V, W);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 36036 KB Output is correct
2 Correct 113 ms 38844 KB Output is correct
3 Correct 65 ms 5460 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1108 ms 368452 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1108 ms 368452 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1108 ms 368452 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1108 ms 368452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1108 ms 368452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1108 ms 368452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1108 ms 368452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1108 ms 368452 KB Time limit exceeded
4 Halted 0 ms 0 KB -