Submission #1060262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060262		qilby	Closing Time (IOI23_closing)	C++17	8 / 100	112 ms	40912 KiB

closing

#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
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17