제출 #1284585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284585		modwwe	봉쇄 시간 (IOI23_closing)	C++20	18 / 100	152 ms	35400 KiB

closing

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCK S_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const ll inf = 1e15+7;
const int mod2 =998244353;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,r2, center;
ll  i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
ll x,y;
struct ib
{
    ll a,b;
};
vector<ll> c;
vector<ib> f;
ll d[2][200001];
ll suff[200001];
vector<ib> v[200001];
vector<ll> vc;
ll cost(ll x)
{
    if(x>k)return -n*2 ;
    return upper_bound(c.begin(),c.end(),k-x)-c.begin()+dem2;
}
void dfs(int x,int y,int z)
{
    for(auto [g,cx]:v[x])
        if(g^y)
        {
            d[z][g]=d[z][x]+cx;
            dfs(g,x,z);
        }
}
bool cmp(ib x,ib y)
{
    return x.a<y.a;
}
int max_score(int N,int X,int Y,ll K,vector<int> U,vector<int>V,vector<int>W)
{
    n=N;
    x=X;
    y=Y;
    k=K;
    dem=0;
    dem2=0;
    s4=0;
    vc.clear();
    c.clear();
    f.clear();
    for(int i=0; i<n; i++)v[i].clear();
    for(int i=0; i<U.size(); i++)
    {
        v[U[i]].pb({V[i],W[i]}),
        v[V[i]].pb({U[i],W[i]});
    }
    d[0][x]=d[1][y]=0;
    dfs(x,x,0);
    dfs(y,y,1);
    dem=0;
    for(int i=0; i<n; i++)
    {
        vc.pb(d[0][i]);
        vc.pb(d[1][i]);
    }
    sort(vc.begin(),vc.end());
    for(auto x:vc)
    {
        if(s4+x<=k)
        {
            s4+=x;
            dem++;
        }
        else
        {
            break;
        }
    }
    s4=0;
    for(int i=0; i<n; i++)
    {
        int minn=min(d[0][i],d[1][i]);
        int maxx=max(d[0][i],d[1][i]);
        if(minn+maxx==d[0][y])
        {
            s4+=minn;
            c.pb(maxx-minn);
            dem2++;
        }
        else if(maxx-minn>=minn)
        {
            c.pb(maxx-minn);
            c.pb(minn);
        }
        else
        {
            f.pb({maxx,minn});
        }
    }
    sort(c.begin(),c.end());
    for(int i=1; i<c.size(); i++)
        c[i]+=c[i-1];
    sort(f.begin(),f.end(),cmp);
    dem=max(dem,cost(s4));
    suff[f.size()]=k+1;
    for(int i=f.size()-1; i>=0; --i)
        suff[i]=min(suff[i+1],f[i].b);
    for(int i=0; i<f.size(); i++)
    {
        s4+=f[i].a;
        s5=max(s5,f[i].a-f[i].b);
        dem=max(dem,cost(s4-s5)+i*2+1);
        dem=max(dem,cost(s4)+i*2+2);
        dem=max(dem,cost(s4+suff[i+1])+i*2+3);
    }
    return dem;
}

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