Submission #1229629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229629		vladilius	Closing Time (IOI23_closing)	C++20	8 / 100	97 ms	23364 KiB

closing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
    x++; y++;
    for (int i = 0; i < (n - 1); i++){
        u[i]++; v[i]++;
    }
    vector<pii> g[n + 1];
    for (int i = 0; i < (n - 1); i++){
        g[u[i]].pb({v[i], w[i]});
        g[v[i]].pb({u[i], w[i]});
    }

    vector<ll> dx(n + 1, inf), dy(n + 1, inf);
    queue<int> q;
    q.push(x); dx[x] = 0;
    while (!q.empty()){
        int v = q.front(); q.pop();
        for (auto [u, w]: g[v]){
            if (dx[u] == inf){
                dx[u] = dx[v] + w;
                q.push(u);
            }
        }
    }
    
    q.push(y); dy[y] = 0;
    while (!q.empty()){
        int v = q.front(); q.pop();
        for (auto [u, w]: g[v]){
            if (dy[u] == inf){
                dy[u] = dy[v] + w;
                q.push(u);
            }
        }
    }
    
    sort(dx.begin() + 1, dx.end());
    sort(dy.begin() + 1, dy.end());
    vector<ll> p1(n + 1), p2(n + 1);
    for (int i = 1; i <= n; i++){
        p1[i] = p1[i - 1] + dx[i];
        p2[i] = p2[i - 1] + dy[i];
    }
    
    int j = n, out = 0;
    for (int i = 1; i <= n; i++){
        if (p1[i] > k) break;
        while (j && (p1[i] + p2[j]) > k) j--;
        
        out = max(out, i + j);
    }
    return out;
}

• 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