oj.uz

Submission #1060262

# Submission time Handle Problem Language Result Execution time Memory
1060262 2024-08-15T12:25:00 Z qilby Closing Time (IOI23_closing) C++17
8 / 100
 112 ms 40912 KB 
#include <bits/stdc++.h>

//#include "closing.h"

using namespace std;
using ll = long long;

const int N = 200009;

bool e[N];
ll n, x, y, k, dx[N], dy[N];
vector < array < ll , 2 > > g[N];

bool dfs_path(int v, int p) {
    e[v] = 1;
    if (v == y) return 1;

    for (auto to : g[v]) {
        ll u = to[0];
        if (u == p) continue;
        if (dfs_path(u, v)) return 1;
    }

    e[v] = 0;
    return 0;
}

void dfsx(int v, int p, ll d) {
    dx[v] = d;
    for (auto to : g[v]) {
        ll u = to[0], c = to[1];
        if (u == p) continue;
        dfsx(u, v, d + c);
    }
}

void dfsy(int v, int p, ll d) {
    dy[v] = d;
    for (auto to : g[v]) {
        ll u = to[0], c = to[1];
        if (u == p) continue;
        dfsy(u, v, d + c);
    }
}

int max_score(int N, int X, int Y, ll K, vector < int > fr, vector < int > to, vector < int > cst) {
    n = N, x = X, y = Y, k = K;

    for (int i = 0; i < n; i++) {
        e[i] = 0;
        g[i].clear();
    }

    for (int i = 0; i < n - 1; i++) {
        g[fr[i]].push_back({to[i], cst[i]});
        g[to[i]].push_back({fr[i], cst[i]});
    }

    dfs_path(x, x);

    dfsx(x, x, 0);
    dfsy(y, y, 0);

    int crr = 0;
    vector < ll > can;

    for (int i = 0; i < n; i++) {
        can.push_back(dx[i]);
        can.push_back(dy[i]);
    }

    sort(can.begin(), can.end());

    ll o = k;
    for (auto x : can) if (o >= x) o -= x, crr++;

    return crr;
}

/*int main() {
    cin >> n >> x >> y >> k;

    vector < int > fr(n - 1), to(n - 1), cst(n - 1);
    for (int i = 0; i < n - 1; i++) cin >> fr[i] >> to[i] >> cst[i];

    cout << max_score(n, x, y, k, fr, to, cst);
}*/

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6748 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 96 ms 33004 KB Output is correct
2 Correct 112 ms 40912 KB Output is correct
3 Correct 55 ms 11604 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6748 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 1 ms 6748 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 1 ms 6748 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 1 ms 6748 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 1 ms 6748 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -