제출 #1064213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064213		amirhoseinfar1385	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	51 ms	23124 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
struct yal{
    int u,v,w;
    int getad(int 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<int>adj[maxn];
vector<pair<long long,long long>>all;
int inp[maxn];
vector<int>ezaf;

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

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


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

void dfs(int u,int vas,long long mas=0,int par=-1){
    if(vas==0){
        all[u].first=mas;
    }else{
        all[u].second=mas;
    }
    for(auto x:adj[u]){
        int 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(int i=0;i<n;i++){
        if(all[i].second<all[i].first){
            swap(all[i].first,all[i].second);
        }
    }
}

int calres(){
    vector<long long>hey;
    for(int i=0;i<n;i++){
        hey.push_back(all[i].first);
    }
    sort(hey.begin(),hey.end());
    long long ret=0,unnow=0;
    for(int i=0;i<n;i++){
        if(hey[i]+unnow<=k){
            unnow+=hey[i];
            ret++;
        }else{
            break;
        }
    }
    vector<pair<int,int>>wtf;
    int cnt=0;
    set<pair<int,int>>st;
    vector<int>last(n+1),tof(n+1);
    for(int 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));
            st.insert(make_pair(dp[i][2],i+1));
            st.insert(make_pair(all[i].second-all[i].first,-i-1));
        }
    }
    if(k<0){
        return ret;
    }
    sort(wtf.begin(),wtf.end());
    unnow=0;
    long long fake=0;
    while(true){
        auto x=*st.begin();
        st.erase(x);
        //cout<<x.first<<" "<<x.second<<" "<<" "<<unnow<<" "<<k<<endl;
        if(unnow+x.first>k){
            break;
        }
        unnow+=x.first;
        fake++;
        if(x.second>0){
            x.second--;
            st.insert(make_pair(all[x.second].second-all[x.second].first,-x.second-1));
            last[x.second]++;
            st.insert(make_pair(dp[x.second][last[x.second]],x.second+1));
        }else{
            //hehe;
        }
    }    
    ret=max(ret,fake+cnt);
    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(int 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(int 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: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17