Submission #840862

#	Time	Username	Problem	Language	Result	Execution time	Memory
840862		79brue	Closing Time (IOI23_closing)	C++17	100 / 100	458 ms	62148 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

struct dat{
    int x; ll v;
    dat(){}
    dat(int x, ll v): x(x), v(v){}
    bool operator<(const dat &r)const{
        if(v!=r.v) return v<r.v;
        return x<r.x;
    }
};

struct Result{
    int A, B; ll profit;
    Result(){}
    Result(int A, int B, ll profit): A(A), B(B), profit(profit){}

    bool operator<(const Result &r)const{
        return profit < r.profit;
    }
};

int n, s, e; ll k;
vector<pair<int, ll> > link[200002];

ll sdist[200002], edist[200002];
ll v1[200002], v2[200002];

void dfs(int x, int p, ll d, ll *dist){
    dist[x] = d;
    for(pair<int, ll> y: link[x]){
        if(y.first == p) continue;
        dfs(y.first, x, d+y.second, dist);
    }
}

ll arr[200002][3];
ll state[200002];
ll allSum;

set<dat> st[3][3];

void update(int x){
    for(int i=0; i<3; i++){
        if(state[x] == i) continue;
        st[state[x]][i].insert(dat(x, arr[x][i] - arr[x][state[x]]));
    }
}

void remove(int x){
    for(int i=0; i<3; i++){
        if(state[x] == i) continue;
        st[state[x]][i].erase(dat(x, arr[x][i] - arr[x][state[x]]));
    }
}

void up(int x){
    allSum += arr[x][state[x]+1] - arr[x][state[x]];
    state[x]++;
}

void down(int x){
    state[x]--;
    allSum -= arr[x][state[x]+1] - arr[x][state[x]];
}

Result check(int a, int b){
    if(st[a][a+1+(b!=-1)].empty() || (b!=-1 && st[b][b-1].empty())) return Result(0, 0, LLONG_MAX);
    Result ret (0, 0, 0);

    auto it = st[a][a+1+(b!=-1)].begin();
    ret.A = it->x, ret.profit += it->v;

    if(b!=-1){
        it = st[b][b-1].begin();
        ret.B = it->x, ret.profit += it->v;
    }
    return ret;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
    n = N, s = X+1, e = Y+1, k = K;
    for(int i=1; i<=n; i++) link[i].clear();
    for(int i=0; i<n-1; i++){
        link[U[i]+1].push_back(make_pair(V[i]+1, W[i]));
        link[V[i]+1].push_back(make_pair(U[i]+1, W[i]));
    }
    dfs(s, -1, 0, sdist);
    dfs(e, -1, 0, edist);

    int ans = 0;
    {
        vector<ll> v;
        for(int i=1; i<=n; i++) v.push_back(sdist[i]), v.push_back(edist[i]);
        sort(v.begin(), v.end());

        ll sum = 0;
        for(int i=0; i<n*2; i++){
            sum += v[i];
            if(sum > K) break;
            ans = i+1;
        }
    }

    /// 이제는 따로 처리
    ll se = sdist[e];
    ll base = 0;
    int baseCnt = 0;
    for(int i=1; i<=n; i++){
        if(sdist[i] + edist[i] != se){
            v1[i] = min(sdist[i], edist[i]);
            v2[i] = max(sdist[i], edist[i]) - v1[i];
        }
        else{
            v1[i] = max(sdist[i], edist[i]) - min(sdist[i], edist[i]);
            v2[i] = K+1;
            base += min(sdist[i], edist[i]);
            baseCnt++;
        }
        arr[i][0] = 0;
        arr[i][1] = v1[i];
        arr[i][2] = v1[i] + v2[i];
        state[i] = 0;
//        printf("%d: %lld %lld %lld\n", i, arr[i][0], arr[i][1], arr[i][2]);
    }

    if(base <= K){
        K -= base;
//        printf("base %d %lld\n", baseCnt, base);

        for(int i=0; i<3; i++) for(int j=0; j<3; j++) st[i][j].clear();

        for(int i=1; i<=n; i++){
            update(i);
        }

        int ret = 0;
        allSum = 0;
        for(int turn=1; turn<=2*n; turn++){
            Result tmp (0, 0, LLONG_MAX);
            tmp = min(tmp, check(0, -1));
            tmp = min(tmp, check(1, -1));
            tmp = min(tmp, check(0, 1));
            tmp = min(tmp, check(0, 2));

            remove(tmp.A);
            if(tmp.B) remove(tmp.B);
            up(tmp.A);
            if(tmp.B) down(tmp.B), up(tmp.A);
            update(tmp.A);
            if(tmp.B) update(tmp.B);

            if(K < allSum) break;
            ret++;
        }
        ans = max(ans, ret+baseCnt);
    }
    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