Submission #1087980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087980		Valaki2	Closing Time (IOI23_closing)	C++17	8 / 100	93 ms	35156 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;

struct edge {
    int to, wei;
};

int ans;

int n, x, y, k;
vector<pii > g[1 + maxn];
int d[2][1 + maxn];
bool done[2][1 + maxn];

void dfs(int cur, int idx, int par) {
    for(pii nei : g[cur]) {
        if(nei.fi != par) {
            d[idx][nei.fi] = d[idx][cur] + nei.se;
            dfs(nei.fi, idx, cur);
        }
    }
}

struct item {
    int val;
    int pos;
    int type;
    bool operator < (const item & other) const {
        return val > other.val;
    }
};

int sum, cur_ans;
priority_queue<item> q;

void push_for(item cur) {
    for(pii nei : g[cur.pos]) {
        if(!done[cur.type][nei.fi]) {
            q.push({d[cur.type][nei.fi], nei.fi, cur.type});
        }
    }
}

bool eval(item cur) {
    if(cur.val > k - sum) {
        return false;
    }
    sum += cur.val;
    cur_ans++;
    done[cur.type][cur.pos] = true;
    push_for(cur);
    return true;
}

void solve() {
    dfs(x, 0, -1);
    dfs(y, 1, -1);
    q.push({0, x, 0});
    q.push({0, y, 1});
    sum = 0, cur_ans = 0;
    while(!q.empty()) {
        item cur = q.top();
        q.pop();
        bool res = eval(cur);
        if(!res) {
            break;
        }
    }
    ans = cur_ans;
}

void reset() {
    ans = 0;
    for(int i = 1; i <= n; i++) {
        g[i].clear();
        d[0][i] = d[1][i] = 0;
        done[0][i] = done[1][i] = false;
    }
    sum = 0, cur_ans = 0;
    while(!q.empty()) {
        q.pop();
    }
    //
}

signed max_score(signed N, signed X, signed Y, int K,
              vector<signed> U, vector<signed> V, vector<signed> W) {
    reset();
    n = N, x = X, y = Y, k = K;
    x++;
    y++;
    for(int i = 0; i < n - 1; i++) {
        int a = U[i], b = V[i], c = W[i];
        a++;
        b++;
        g[a].pb(mp(b, c));
        g[b].pb(mp(a, c));
    }
    solve();
    return ans;
}

• 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