oj.uz

답안 #840085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840085 2023-08-31T06:22:58 Z bachhoangxuan 봉쇄 시간 (IOI23_closing) C++17
37 / 100
 803 ms 47048 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 dp2[maxs][2*maxs],dp1[maxs][maxs],nw2[2*maxs],nw1[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){
        priority_queue<long long,vector<long long>,greater<long long>> pq2;
        function<void(int,int)> dfs = [&](int u,int p){
            pq2.push(min(dist[u][0],dist[u][1]));
            for(auto &[v,w]:edge[u]){
                if(v==p || check[v]) continue;
                dfs(v,u);sz[u]+=sz[v];
            }
        };

        int pos=path[0];
        for(int u:path){
            dfs(u,-1);
            for(int i=0;i<=2*n;i++) dp1[u][i]=dp2[u][i]=inf;
            int d=abs(dist[u][0]-dist[u][1]);
            for(int i=1;i<=sz[u];i++) dp1[u][i]=(i==1?0:dp1[u][i-1])+pq2.top(),pq2.pop();
            for(int i=sz[u];i>=1;i--){
                for(int j=1;j<=i;j++) dp2[u][i+j]=min(dp2[u][i+j],dp1[u][i]+d*j);
            }
            if(dist[u][0]<=dist[u][1]) pos=u;
            /*
            cout << u << '\n';
            for(int i=1;i<=sz[u];i++) cout << dp1[u][i] << ' ';
            cout << '\n';
            for(int i=1;i<=2*sz[u];i++) cout << (dp2[u][i]==inf?-1:dp2[u][i]) << ' ';
            cout << '\n';
            */
        }

        function<void(int,int)> unions2 = [&](int u,int v){
            for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
            for(int i=1;i<=sz[u]+sz[v];i++) nw1[i]=inf;

            for(int i=2*sz[u];i>=1;i--){
                for(int j=1;j<=2*sz[v];j++){
                    nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
                    if(j<=sz[v]){
                        nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp1[v][j]);
                        if(i<=sz[u]) nw1[i+j]=min(nw1[i+j],dp1[u][i]+dp1[v][j]);
                    }
                }
            }
            sz[u]+=sz[v];
            for(int i=1;i<=2*sz[u];i++) dp2[u][i]=nw2[i];
            for(int i=1;i<=sz[u];i++) dp1[u][i]=nw1[i];
        };

        for(int i=0;i<(int)path.size();i++){
            if(i) unions2(path[i],path[i-1]);
            if(path[i]==pos) break;
        }
        //cout << sz[0] << ' ' << sz[1] << '\n';

        for(int t=(int)path.size()-1;t>=0;t--){
            if(path[t]==pos){
                int u=path[t],v=path[t+1];
                for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
                for(int j=1;j<=sz[u];j++) dp2[u][j]=min(dp2[u][j],dp1[u][j]);
                for(int j=1;j<=sz[v];j++) dp2[v][j]=min(dp2[v][j],dp1[v][j]);

                /*
                for(int i=1;i<=2*sz[u];i++) cout << dp2[u][i] << ' ';
                cout << '\n';
                for(int i=1;i<=2*sz[v];i++) cout << dp2[v][i] << ' ';
                cout << '\n';
                */

                for(int i=2*sz[u];i>=1;i--){
                    for(int j=1;j<=2*sz[v];j++) nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
                }
                sz[u]+=sz[v];
                //cout << sz[u] << ' ' << sz[v] << '\n';
                for(long long j=1;j<=2*sz[u];j++){
                    //cout << nw2[j] << ' ';
                    if(nw2[j]<=K) res=max(res,j);
                }
                //cout << '\n';
                break;
            }
            if(t!=(int)path.size()-1)unions2(path[t],path[t+1]);
        }
    }
    return res;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 30848 KB Output is correct
2 Correct 124 ms 39988 KB Output is correct
3 Correct 803 ms 47048 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 2 ms 5332 KB Output is correct
10 Correct 2 ms 5460 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 2 ms 5332 KB Output is correct
10 Correct 2 ms 5460 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 2 ms 5076 KB Output is correct
14 Correct 2 ms 5588 KB Output is correct
15 Correct 2 ms 5204 KB Output is correct
16 Correct 3 ms 6100 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Incorrect 7 ms 12352 KB 1st lines differ - on the 1st token, expected: '884', found: '958'
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 2 ms 5332 KB Output is correct
10 Correct 2 ms 5460 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 2 ms 5076 KB Output is correct
14 Correct 2 ms 5588 KB Output is correct
15 Correct 2 ms 5204 KB Output is correct
16 Correct 3 ms 6100 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Incorrect 7 ms 12352 KB 1st lines differ - on the 1st token, expected: '884', found: '958'
22 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4996 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct
13 Correct 2 ms 5060 KB Output is correct
14 Correct 2 ms 5076 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 5076 KB Output is correct
18 Correct 2 ms 5076 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 2 ms 5332 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 2 ms 5460 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 2 ms 5076 KB Output is correct
15 Correct 2 ms 5588 KB Output is correct
16 Correct 2 ms 5204 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 3 ms 4996 KB Output is correct
23 Correct 2 ms 5076 KB Output is correct
24 Correct 2 ms 5076 KB Output is correct
25 Correct 2 ms 5060 KB Output is correct
26 Correct 2 ms 5076 KB Output is correct
27 Correct 2 ms 5076 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 5076 KB Output is correct
30 Correct 2 ms 5076 KB Output is correct
31 Correct 2 ms 5076 KB Output is correct
32 Correct 2 ms 5076 KB Output is correct
33 Correct 2 ms 5076 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 5080 KB Output is correct
38 Correct 2 ms 5076 KB Output is correct
39 Correct 2 ms 5076 KB Output is correct
40 Correct 2 ms 5076 KB Output is correct
41 Correct 2 ms 5076 KB Output is correct
42 Correct 3 ms 5076 KB Output is correct
43 Correct 3 ms 5948 KB Output is correct
44 Correct 2 ms 5204 KB Output is correct
45 Correct 3 ms 5460 KB Output is correct
46 Correct 2 ms 5204 KB Output is correct
47 Correct 2 ms 5076 KB Output is correct
48 Correct 2 ms 5076 KB Output is correct
49 Correct 2 ms 5076 KB Output is correct
50 Correct 2 ms 5076 KB Output is correct

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 2 ms 5332 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 2 ms 5460 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 2 ms 5076 KB Output is correct
15 Correct 2 ms 5588 KB Output is correct
16 Correct 2 ms 5204 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 4 ms 5076 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Incorrect 7 ms 12352 KB 1st lines differ - on the 1st token, expected: '884', found: '958'
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 2 ms 5332 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 2 ms 5460 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 2 ms 5076 KB Output is correct
15 Correct 2 ms 5588 KB Output is correct
16 Correct 2 ms 5204 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 4 ms 5076 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Incorrect 7 ms 12352 KB 1st lines differ - on the 1st token, expected: '884', found: '958'
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 2 ms 5332 KB Output is correct
11 Correct 2 ms 5460 KB Output is correct
12 Correct 2 ms 5460 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 2 ms 5076 KB Output is correct
15 Correct 2 ms 5588 KB Output is correct
16 Correct 2 ms 5204 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 4 ms 5076 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Incorrect 7 ms 12352 KB 1st lines differ - on the 1st token, expected: '884', found: '958'
23 Halted 0 ms 0 KB -