Submission #1064461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064461		amirhoseinfar1385	Closing Time (IOI23_closing)	C++17	18 / 100	51 ms	22936 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=3000+10;
struct yal{
    long long u,v,w;
    long long getad(long long fu){
        return (u^v^fu);
    }
}alle[maxn];
long long n,x,y,k,dp1[maxn][maxn],inf=1e18+1,dp2[maxn][maxn],dp[maxn][maxn];
vector<long long>adj[maxn];
vector<pair<long long,long long>>all;
long long inp[maxn];
vector<long long>ezaf;

void clear(){
    all.clear();
    for(long long i=0;i<=n;i++){
        inp[i]=0;
        adj[i].clear();
        for(long long j=0;j<=n;j++){
            dp1[i][j]=dp2[i][j]=dp[i][j]=inf;
        }
    }
}
void dfsdp(long long u,long long par=-1){
    if(par==-1){
        ezaf.push_back(0);
    }else{
        ezaf.push_back(all[u].first);
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par&&inp[v]==0){
            dfsdp(v,u);
        }
    }
}

void boro(long long u){
    dfsdp(u);
    sort(ezaf.begin(),ezaf.end());
    for(long long i=1;i<=(long long)ezaf.size();i++){
        dp[u][i]=dp[u][i-1]+ezaf[i-1];
    }
    for(long long i=(long long)ezaf.size()+1;i<=n+1;i++){
        dp[u][i]=inf;
    }
    ezaf.clear();
}


long long findpath(long long u,long long had,long long par=-1){
    long long ret=0;
    if(had==u){
        ret=1;
        inp[u]=1;
        return 1;
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par){
            ret|=findpath(v,had,u);
        }
    }
    if(ret){
        inp[u]=1;
    }
    return ret;
}

void dfs(long long u,long long vas,long long mas=0,long long par=-1){
    if(vas==0){
        all[u].first=mas;
    }else{
        all[u].second=mas;
    }
    for(auto x:adj[u]){
        long long v=alle[x].getad(u);
        if(v!=par){
            dfs(v,vas,mas+alle[x].w,u);
        }
    }
}

void calall(){
    dfs(x,0);
    dfs(y,1);
    for(long long i=0;i<n;i++){
        if(all[i].second<all[i].first){
            swap(all[i].first,all[i].second);
        }
    }
}

long long calres(){
    vector<long long>hey;
    for(long long i=0;i<n;i++){
        hey.push_back(all[i].first);
    }
    sort(hey.begin(),hey.end());
    long long ret=0,unnow=0;
    for(long long i=0;i<n;i++){
        if(hey[i]+unnow<=k){
            unnow+=hey[i];
            ret++;
        }else{
            break;
        }
    }
    vector<pair<long long,long long>>wtf;
    long long cnt=0;
    set<pair<long long,long long>>st;
    vector<long long>last(n+1),tof(n+1);
    for(long long i=0;i<n;i++){
        if(inp[i]){
            k-=all[i].first;
            cnt++;
            last[i]=2;
            wtf.push_back(make_pair(all[i].second-all[i].first,i));
        }
    }
    if(k<0){
        return ret;
    }
    sort(wtf.rbegin(),wtf.rend());
    vector<pair<long long,long long>>allv;
    for(long long i=0;i<(long long)wtf.size();i++){
        for(long long j=1;j<=n;j++){
            if(dp[wtf[i].second][j]>=inf){
                break;
            }
            allv.push_back(make_pair(dp[wtf[i].second][j]-dp[wtf[i].second][j-1],dp[wtf[i].second][j]-dp[wtf[i].second][j-1]+wtf[i].first));
        }
    } 
    for(long long i=0;i<=n+1;i++){
        for(long long j=0;j<=n+1;j++){
            dp2[i][j]=dp1[i][j]=inf;
        }
    }
    dp1[0][0]=dp2[(long long)allv.size()+1][0]=0;
    for(long long i=1;i<=(long long)allv.size();i++){
       // cout<<allv[i-1].first<<" "<<allv[i-1].second<<endl;
        for(long long j=0;j<=i;j++){
            dp1[i][j]=dp1[i-1][j];
            if(j>0){
                dp1[i][j]=min(dp1[i][j],dp1[i-1][j-1]+allv[i-1].first);
            }
        }
    }
    for(long long i=(long long)allv.size();i>=1;i--){
        for(long long j=0;j<=n;j++){
            dp2[i][j]=dp2[i+1][j];
            if(j>0){
                dp2[i][j]=min(dp2[i][j],dp2[i+1][j-1]+allv[i-1].second);
            }
        }
    }
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=n;j++){
            for(long long h=0;h<=n;h++){
                if(dp1[i][j]+dp2[i+1][h]>k){
                    continue;
                }else{
                    ret=max(ret,j+h*2);
                }
            }
        }
    }
    return ret;
}

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;
    for(long long i=0;i<n-1;i++){
        alle[i].u=U[i];
        alle[i].v=V[i];
        alle[i].w=W[i];
        adj[alle[i].u].push_back(i);
        adj[alle[i].v].push_back(i);
    }
    all.resize(n);
    calall();
    findpath(x,y);
    for(long long i=0;i<n;i++){
        if(inp[i]){
            boro(i);
        }
    }
    long long ret=calres();
    clear();
    return ret;
}

• 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