Submission #1027847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027847		Gray	Closing Time (IOI23_closing)	C++17	100 / 100	145 ms	54600 KiB

closing

#include "closing.h"
// #include <iostream>
#include <climits>
#include <queue>
#include <stack>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;

vector<vector<ll>> A;
vector<pair<ll, pair<ll, ll>>> e;
ll n, x, y, k;
vector<ll> distX, distY, app1, app2;
vector<ll> type, xypath;
// void debug(){
//     for (ll i=0; i<n; i++){
//         cout << app1[i] << " ";
//     }
//     cout << ln;
//     for (ll i=0; i<n; i++){
//         cout << app2[i] << " ";
//     }
//     cout << ln;
// }
void calcDist(ll u, ll p, ll depth, vector<ll> &depthWrite){
    // cout << u << endl;
    depthWrite[u]=depth;
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        calcDist(v, u, depth+e[i].ff, depthWrite);
    }
}
void genDist(){
    distX.resize(n); distY.resize(n); app1.resize(n); app2.resize(n); type.assign(n, 0);
    // return;
    calcDist(x, x, 0, distX);
    calcDist(y, y, 0, distY);
    // return;
    for (ll i=0; i<n; i++){
        app1[i]=min(distX[i], distY[i]);
        app2[i]=max(distX[i], distY[i])-app1[i];
        if (app1[i]>=app2[i]) type[i]=2;
        if  (app1[i]*2+app2[i]==distX[y]) {type[i]=1; xypath.push_back(i);}
    }
    // debug();
}

ll case1(){
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    que.push({0, x});
    que.push({0, y});
    vector<bool> vis(n);
    ll ck=k, ans=0;
    while(!que.empty()){
        auto cur = que.top();
        que.pop();
        if (vis[cur.ss]) continue;
        if (cur.ff>ck) break;
        ck-=cur.ff;
        ans++;
        vis[cur.ss]=1;
        for (auto i:A[cur.ss]){
            ll v = e[i].ss.ff^e[i].ss.ss^cur.ss;
            if (!vis[v]) que.push({cur.ff+e[i].ff, v});
        }
    }
    return ans;
}

ll case2(){
    ll ck=k;
    ll ans=0;
    vector<ll> usd(n);
    for (auto v:xypath){
        ck-=app1[v];
        ans++;
        usd[v]++;
    }
    if (ck>0){
        // cout << "Hap" << ln;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q1, q2;
        // q1-type 0 & 1; q2-type 2
        for (ll i=0; i<n; i++){
            if (type[i]==0){
                q1.push({app1[i], i});
                q1.push({app2[i], i});
            }else if (type[i]==1){
                q1.push({app2[i], i});
            }else{
                q2.push({app1[i]+app2[i], i});
            }
        }
        while (!q2.empty() and ck>0){
            if (q1.size()>=2){
                pair<ll, ll> q1l2;
                q1l2=q1.top(); q1.pop(); 
                if (q2.top().ff<=q1l2.ff+q1.top().ff and q2.top().ff<=ck){
                    q1.push(q1l2);
                    usd[q2.top().ss]=2;
                    ans+=2;
                    ck-=q2.top().ff;
                    q2.pop();
                }else{
                    if (q1l2.ff+q1.top().ff<=ck){
                        usd[q1l2.ss]++;
                        ans++;
                        ck-=q1l2.ff;
                    }else{
                        q1.push(q1l2);
                        break;
                    }
                }
            }else{
                if (ck>=q2.top().ff){
                    ck-=q2.top().ff;
                    ans+=2;
                    usd[q2.top().ss]=2;
                    q2.pop();
                }else{
                    break;
                }
            }
        }
        while (!q1.empty() and ck>0){
            if (q1.top().ff<=ck){
                ck-=q1.top().ff;
                ans++;
                usd[q1.top().ss]++;
                q1.pop();
            }else break;
        }
        ll mn = LLONG_MAX;
        for (ll i=0; i<n; i++){
            if (type[i]==2 and usd[i]==0){
                mn=min(mn, app1[i]);
            }
        }
        if (mn<=ck){
            ans++;
        }
        return ans;
    }else return 0;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N; x=X; y=Y; k=K;
    A.clear(); e.clear(); distX.clear(); distY.clear(); app1.clear(); app2.clear(); type.clear(); xypath.clear();
    A.resize(n); e.resize(n-1);
    for (ll i=0; i<n-1; i++){
        e[i]={W[i], {U[i], V[i]}};
        A[U[i]].push_back(i);
        A[V[i]].push_back(i);
    }
    // return 0;
    genDist();
    // return 0;
    ll res=max(case2(), case1());
    return (int)res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17