Submission #1229523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229523		vladilius	Closing Time (IOI23_closing)	C++20	21 / 100	1096 ms	24288 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]});
    }
    
    int S = 0;
    for (int i = 1; i <= n; i++){
        if (g[i].size() == 1){
            S = i;
            break;
        }
    }
    
    vector<int> f(n + 2); f[1] = S;
    for (int i = 2; i <= n; i++){
        for (auto [j, w]: g[f[i - 1]]){
            if (j != f[i - 2]){
                f[i] = j;
                break;
            }
        }
    }
    
    f[n + 1] = 0;
    
    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);
            }
        }
    }
    
    int out = 0, px = 0, py = 0;
    for (int i = 1; i <= n; i++){
        if (f[i] == x){
            px = i;
        }
        if (f[i] == y){
            py = i;
        }
    }
    
    for (int l = 1; l <= px; l++){
        for (int r = px; r <= n; r++){
            vector<ll> d(n + 1);
            ll tot = 0; int cc = r - l + 1;
            for (int i = l; i <= r; i++){
                d[f[i]] = dx[f[i]];
                tot += d[f[i]];
            }
            vector<ll> p(n + 1);
            for (int i = 0; i <= n; i++){
                p[i] = max(0LL, dy[i] - d[i]);
            }
            
            if (tot > k) continue;
            
            cc++; // y
            
            int i = py - 1, j = py + 1;
            while (tot <= k && (i || j <= n)){
                out = max(out, cc);
                if (p[f[i]] > p[f[j]]){
                    tot += p[f[j]];
                    j++;
                    cc++;
                }
                else {
                    tot += p[f[i]];
                    i--;
                    cc++;
                }
            }
            
            if (tot <= k){
                out = max(out, cc);
            }
        }
    }
    
    return out;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 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