Submission #1144745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144745		Math4Life2020	Closing Time (IOI23_closing)	C++20	100 / 100	317 ms	68640 KiB

closing

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 2e18;

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    ll ans = 0;
    vector<pii> adj[N];
    vector<pii> fadj[N];
    pii radj[N];
    ll ht[N];
    ll dx[N]; //distance x
    for (ll i=0;i<(N-1);i++) {
        adj[U[i]].push_back({V[i],W[i]});
        adj[V[i]].push_back({U[i],W[i]});
    }
    ht[X]=0;
    dx[X]=0;
    radj[X]={-1,-1};
    queue<ll> q0;
    q0.push(X);
    while (!q0.empty()) {
        ll z = q0.front(); q0.pop();
        for (pii p0: adj[z]) {
            if (radj[z].first==p0.first) {
                continue;
            }
            fadj[z].push_back(p0);
            ht[p0.first]=ht[z]+1;
            radj[p0.first]={z,p0.second};
            dx[p0.first]=dx[z]+p0.second;
            q0.push(p0.first);
        }
    }
    ll D = ht[Y];
    ll stpt[D+1];
    stpt[D]=Y;
    for (ll d=(D-1);d>=0;d--) {
        stpt[d]=radj[stpt[d+1]].first;
    }
    ll dy[N];
    dy[Y]=0;
    queue<pii> q1; //point, search parent
    q1.push({Y,-1});
    while (!q1.empty()) {
        pii pc = q1.front(); q1.pop();
        for (pii p1: adj[pc.first]) {
            if (p1.first==pc.second) {
                continue;
            }
            dy[p1.first]=dy[pc.first]+p1.second;
            q1.push({p1.first,pc.first});
        }
    }
    pii dc[N];
    for (ll i=0;i<N;i++) {
        dc[i]={min(dy[i],dx[i]),max(dy[i],dx[i])-min(dy[i],dx[i])};
        //cout << "dc[i="<<i<<"]="<<dc[i].first<<","<<dc[i].second<<"\n";
    }
    set<pii> s0; //{value, x}
    vector<bool> found0(N,0);
    ll val0 = K;
    ll num0 = 0;
    s0.insert({0,X});
    s0.insert({0,Y});
    while (!s0.empty()) {
        pii p0 = *s0.begin(); s0.erase(s0.begin());
        //cout << "p0: "<<p0.first<<", "<<p0.second<<"\n";
        ll z = p0.second;
        if (found0[z]) {
            continue;
        }
        if (val0<p0.first) {
            break;
        }
        val0 -= p0.first;
        //cout << "new val0="<<val0<<"\n";
        num0++;
        found0[z]=1;
        for (pii p1: adj[z]) {
            if (!found0[p1.first]) {
                s0.insert({dc[p1.first].first,p1.first});
            }
        }
    }
    ans = max(ans,num0);
    //cout << "ans0="<<ans<<"\n";
    set<pii> s1; //"individual hit" on point
    set<pii> s2; //"double hit" on point
    vector<bool> found1(N,0);
    vector<bool> found2(N,0);
    ll num1 = 0;
    ll val1 = 0;
    for (ll d=0;d<=D;d++) {
        num1++;
        val1 += dc[stpt[d]].first;
        s1.insert({dc[stpt[d]].second,stpt[d]});
        //cout << "s1 term: "<<dc[stpt[d]].second<<"\n";
        found1[stpt[d]]=1;
        for (pii p0: fadj[stpt[d]]) {
            if (d<D && p0.first==stpt[d+1]) {
                continue;
            }
            s1.insert({dc[p0.first].first,p0.first});
            s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
        }
    }
    if (val1>K) {
        return ans;
    }
    val1 = K-val1;
    //cout << "val1="<<val1<<"\n";
    ll smax = -INF; //solo maximum
    while (!s1.empty() || !s2.empty()) {
        assert(val1>=0);
        //"fix" both
        while (!s2.empty()) {
            ll z = (*s2.begin()).second;
            if (found1[z]) {
                s2.erase(s2.begin());
            } else {
                break;
            }
        }
        while (!s1.empty()) {
            pii pt = (*s1.begin()); 
            ll z = pt.second; ll cval = pt.first;
            if (found2[z]) {
                //cout << "huh\n";
                s1.erase(s1.begin());
            } else if (found1[z]) {
                if (cval != dc[z].second) {
                    //cout << "flagging\n";
                    s1.erase(s1.begin());
                } else {
                    //cout << "breaking\n";
                    break;
                }
            } else {
                //cout << "huhuh\n";
                if (cval != dc[z].first) {
                    s1.erase(s1.begin());
                } else {
                    break;
                }
            }
        }
        if (s1.empty() && s2.empty()) {
            break;
        } else if (s2.empty()) {
            pii pt = *s1.begin(); s1.erase(s1.begin());
            ll z = pt.second; ll cval = pt.first;
            if (cval>val1) {
                break;
            } 
            num1++;
            val1-=cval;
            smax = max(smax,cval);
            if (found1[z]) {
                found2[z]=1;
                for (pii p0: adj[z]) {
                    s1.insert({dc[p0.first].first,p0.first});
                    s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
                }
            } else {
                found1[z]=1;
                s1.insert({dc[z].second,z});
                for (pii p0: adj[z]) {
                    s1.insert({dc[p0.first].first,p0.first});
                    //s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
                }
            }
        } else {
            assert(!s1.empty() && !s2.empty());
            //s1 empty, s2 nonempty impossible
            pii p1 = *s1.begin(); pii p2 = *s2.begin();
            if ((2*p1.first)<=p2.first) { //p1 "better"
                ll z = p1.second; ll cval = p1.first;
                s1.erase(s1.begin());
                if (cval>val1) {
                    break;
                } 
                num1++;
                val1-=cval;
                smax = max(smax,cval);
                if (found1[z]) {
                    found2[z]=1;
                    for (pii p0: adj[z]) {
                        s1.insert({dc[p0.first].first,p0.first});
                        s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
                    }
                } else {
                    found1[z]=1;
                    s1.insert({dc[z].second,z});
                    for (pii p0: adj[z]) {
                        s1.insert({dc[p0.first].first,p0.first});
                        //s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
                    }
                }
            } else {
                ll z = p2.second; ll cval = p2.first;
                s2.erase(s2.begin());
                if (cval>val1) {
                    ans = max(num1,ans);
                    if (p1.first<=val1) {
                        ans = max(num1+1,ans);
                    }
                    smax = max(smax,dc[z].second);
                    val1 -= cval;
                    if ((val1+smax)>=0) {
                        ans = max(num1+1,ans);
                    }
                    break;
                }
                num1 += 2;
                val1 -= cval;
                smax = max(smax,dc[z].second);
                found1[z]=1;
                found2[z]=1;
                for (pii p0: adj[z]) {
                    s1.insert({dc[p0.first].first,p0.first});
                    s2.insert({dc[p0.first].first+dc[p0.first].second,p0.first});
                }
            }
        }
    }
    ans = max(num1,ans);
    return ans;
}

• 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