oj.uz

Submission #840070

# Submission time Handle Problem Language Result Execution time Memory
840070 2023-08-31T05:06:44 Z bachhoangxuan Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 39956 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int maxs=3005;
#define pii pair<int,int>
#define piii pair<long long,pii>
#define fi first
#define se second
const long long inf=2e18;

long long dist[maxn][2];
long long dp1[maxs][maxs],dp2[maxs][2*maxs];
int sz[maxn];

vector<pii> edge[maxn];
bool check[maxn];

bool cc[maxn][2];

int max_score(int n, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{
    for(int i=0;i<n;i++){
        edge[i].clear();check[i]=cc[i][0]=cc[i][1]=false;
        dist[i][0]=dist[i][1]=0;sz[i]=1;
    }

    for(int i=0;i<n-1;i++){
        edge[U[i]].push_back({V[i],W[i]});
        edge[V[i]].push_back({U[i],W[i]});
    }

    vector<int> path;
    function<void(int,int)> pre_dfs = [&](int u,int p){
        if(u==Y){
            path.push_back(u);
            check[u]=true;
            return;
        }
        for(auto &[v,w]:edge[u]){
            if(v==p) continue;
            pre_dfs(v,u);check[u]|=check[v];
        }
        if(check[u]) path.push_back(u);
    };
    pre_dfs(X,-1);
    reverse(path.begin(),path.end());

    function<void(int,int,int)> dfs_dist = [&](int u,int p,int t){
        for(auto &[v,w]:edge[u]){
            if(v==p) continue;
            dist[v][t]=dist[u][t]+w;
            dfs_dist(v,u,t);
        }
    };
    dfs_dist(X,-1,0);dfs_dist(Y,-1,1);
    long long res=0,sum=0;
    priority_queue<piii,vector<piii>,greater<piii>> pq;
    pq.push({0,{X,0}});pq.push({0,{Y,1}});

    while(!pq.empty()){
        long long d=pq.top().fi;
        int u=pq.top().se.fi,t=pq.top().se.se;pq.pop();
        if(sum+d>K) break;
        sum+=d;res++;cc[u][t]=true;
        for(auto &[v,w]:edge[u]){
            if(!cc[v][t]) pq.push({dist[v][t],{v,t}});
        }
    }
    if(n<=3000){
        function<void(int,int)> unions = [&](int u,int v){
            for(int i=sz[u];i>=0;i--){
                for(int j=0;j<=sz[v];j++) dp1[u][i+j]=min(dp1[u][i+j],dp1[u][i]+dp1[v][j]);
            }
            for(int i=2*sz[u];i>=0;i--){
                for(int j=0;j<=2*sz[v];j++) dp2[u][i+j]=min(dp2[u][i+j],dp2[u][i]+dp2[v][j]);
            }
            sz[u]+=sz[v];
        };
        function<void(int,int)> dfs = [&](int u,int p){
            for(int i=0;i<=n;i++) dp1[u][i]=inf;
            for(int i=0;i<=2*n;i++) dp2[u][i]=inf;

            sz[u]=1;
            dp2[u][2]=max(dist[u][0],dist[u][1]);
            dp1[u][1]=min(dist[u][0],dist[u][1]);

            for(auto &[v,w]:edge[u]){
                if(v==p || check[v]) continue;
                dfs(v,u);unions(u,v);
            }

            if(p!=-1){
                dp1[u][0]=dp2[u][0]=0;
                for(int i=1;i<=sz[u];i++) dp2[u][i]=min(dp2[u][i],dp1[u][i]);
            }
        };

        int pos=path[0];
        for(int u:path){
            dfs(u,-1);
            if(dist[u][0]<=dist[u][1]) pos=u;
        }

        function<void(int,int)> unions2 = [&](int u,int v){
            for(int i=2*sz[u];i>=0;i--){
                for(int j=0;j<=2*sz[v];j++){
                    dp2[u][i+j]=min(dp2[u][i+j],dp2[u][i]+dp2[v][j]);
                    if(j<=sz[v]){
                        dp2[u][i+j]=min(dp2[u][i+j],dp2[u][i]+dp1[v][j]);
                        if(i<=sz[u]) dp1[u][i+j]=min(dp1[u][i+j],dp1[u][i]+dp1[v][j]);
                    }
                }
            }
            sz[u]+=sz[v];
        };

        for(int i=1;i<(int)path.size();i++){
            unions2(path[i],path[i-1]);
            if(path[i]==pos) break;
        }

        for(int i=(int)path.size()-2;i>=0;i--){
            if(path[i]==pos){
                int u=path[i],v=path[i+1];
                for(int j=0;j<=sz[u];j++) dp2[u][j]=min(dp2[u][j],dp1[u][j]);
                for(int j=0;j<=sz[v];j++) dp2[v][j]=min(dp2[v][j],dp1[v][j]);
                unions(u,v);
                for(long long j=0;j<=2*sz[u];j++){
                    if(j<=sz[u] && dp1[u][j]<=K) res=max(res,j);
                    if(dp2[u][j]<=K) res=max(res,j);
                }
                break;
            }
            unions2(path[i],path[i+1]);
        }
    }
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 30532 KB Output is correct
2 Correct 145 ms 39956 KB Output is correct
3 Execution timed out 1082 ms 39208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '8'
3 Halted 0 ms 0 KB -