제출 #999861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999861		Theo830	봉쇄 시간 (IOI23_closing)	C++17	35 / 100	1042 ms	36160 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vector<ii> >adj;
priority_queue<ii,vector<ii>,greater<ii> >pq;
ll par[200005];
void dfs(ll idx,ll p){
    par[idx] = p;
    for(auto x:adj[idx]){
        if(x.F != p){
            dfs(x.F,idx);
        }
    }
}
int max_score(int n, int x, int y, long long k,vector<int>u, vector<int> v, vector<int> w){
    adj.assign(n+5,vector<ii>());
    f(i,0,n-1){
        adj[u[i]].pb(ii(v[i],w[i]));
        adj[v[i]].pb(ii(u[i],w[i]));
    }
    ll dist[n][3];
    f(i,0,n){
        dist[i][0] = dist[i][1] = 1e18;
    }
    dfs(y,-1);
    dist[x][0] = 0;
    pq.push(ii(0,x));
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w = f.F,u = f.S;
        if(dist[u][0] < w){
            continue;
        }
        for(auto x:adj[u]){
            if(x.S + dist[u][0] < dist[x.F][0]){
                dist[x.F][0] = x.S + dist[u][0];
                pq.push(ii(dist[x.F][0],x.F));
            }
        }
    }
    dist[y][1] = 0;
    pq.push(ii(0,y));
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w = f.F,u = f.S;
        if(dist[u][1] < w){
            continue;
        }
        for(auto x:adj[u]){
            if(x.S + dist[u][1] < dist[x.F][1]){
                dist[x.F][1] = x.S + dist[u][1];
                pq.push(ii(dist[x.F][1],x.F));
            }
        }
    }
    ll sum = 0;
    f(i,0,n){
        dist[i][2] = max(dist[i][0],dist[i][1]);
    }
    set<ll>nodes;
    vector<ll>path;
    ll r = x;
    while(r != -1){
        path.pb(r);
        nodes.insert(r);
        r = par[r];
    }
    assert(path[0] == x && path.back() == y);
    vector<ll>other,q;
    f(i,0,n){
        if(!nodes.count(i)){
            other.pb(min(dist[i][0],dist[i][1]));
        }
    }
    sort(all(other));
    q.pb(0);
    for(auto x:other){
        q.pb(q.back() + x);
    }
    for(auto x:path){
        sum += dist[x][1];
    }
    int ans = 0;
    f(i,0,(ll)(path.size())){
        ll cur = sum;
        f(j,i,(ll)(path.size())){
            cur -= dist[path[j]][1];
            cur += dist[path[j]][2];
            ll num = k - cur;
            if(num >= 0){
                int siz = path.size();
                siz += j - i + 1;
                int pos = upper_bound(all(q),num) - q.begin() - 1;
                siz += pos;
                ans = max(ans,siz);
            }
        }
        sum -= dist[path[i]][1];
        sum += dist[path[i]][0];
    }
    sum = 0;
    for(auto x:path){
        sum += dist[x][2];
    }
    int siz = 2 * (ll)(path.size());
    ll num = k - sum;
    if(num >= 0){
        ans = max(ans,siz);
        ll d = dist[y][0];
        f(i,0,(ll)(other.size())){
            num -= other[i];
            if(num >= 0){
                ans = max(ans,siz + (int)(i+1) + min((int)(i+1),(int)(num / d)));
            }
        }
    }
    int res = 0;
    vector<ll>kame;
    f(i,0,n){
        kame.pb(min(dist[i][0],dist[i][1]));
    }
    sort(all(kame));
    f(i,0,n){
        if(kame[i] <= k){
            k -= kame[i];
            res++;
        }
    }
    ans = max(ans,res);
    return ans;
}
/*
int main()
{

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
*/
/*
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19

1
4 0 3 20
0 1 18
1 2 1
2 3 19
*/

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