oj.uz

답안 #1064249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064249 2024-08-18T10:51:58 Z amirhoseinfar1385 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 46 ms 19512 KB 
#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+1;i++){
        dp[u][i]=inf;
    }
    ezaf.clear();
}


int findpath(int u,int had,int par=-1){
    int ret=0;
    if(had==u){
        ret=1;
        inp[u]=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));
        }
    }
    if(k<0){
        return ret;
    }
    sort(wtf.rbegin(),wtf.rend());
    vector<pair<int,int>>allv;
    for(int i=0;i<(int)wtf.size();i++){
        for(int j=1;j<=n;j++){
            if(dp[wtf[i].second][j]>=inf){
                break;
            }
            cout<<wtf[i].second<<" "<<j<<" "<<dp[wtf[i].second][j]<<endl;
            allv.push_back(make_pair(dp[wtf[i].second][j],dp[wtf[i].second][j]+wtf[i].first));
        }
    } 
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            dp2[i][j]=dp1[i][j]=inf;
        }
    }
    dp1[0][0]=dp2[(int)allv.size()+1][0]=0;
    for(int i=1;i<=(int)allv.size();i++){
       // cout<<allv[i-1].first<<" "<<allv[i-1].second<<endl;
        for(int 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(int i=(int)allv.size();i>=1;i--){
        for(int j=0;j<=i;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(int i=0;i<=n;i++){
        for(long long j=0;j<=n;j++){
            for(int h=0;h<=n;h++){
                if(dp1[i][j]+dp2[i+1][h]>k){
                    break;
                }else{
                    ret=max(ret,j+h*2);
                }
            }
        }
    }
   // cout<<dp1[5][4]<<" "<<dp2[6][1]<<endl;
    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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 19512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB Possible tampering with the output
2 Halted 0 ms 0 KB -