oj.uz

Submission #565812

# Submission time Handle Problem Language Result Execution time Memory
565812 2022-05-21T11:04:49 Z shahriarkhan Village (BOI20_village) C++14
50 / 100
 142 ms 39840 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e5 + 5 , INF = 1e9 + 5 , LG = 25 ;

int dp[MX][2] , mn[MX] ;

vector<int> adj[MX] ;

vector<pair<int,int> > pick[MX][2] ;

void dfs(int s , int p)
{
    int sum = 0 , good = 0 , leaf = 1 , rd = 0 , pos = 0 , idx = 0 ;
    dp[s][0] = 0 , dp[s][1] = INF ;
    for(int t : adj[s])
    {
        if(t==p) continue ;
        dfs(t,s) , leaf = 0 ;
        dp[s][0] = min(dp[s][0] + dp[t][1] , INF) , pick[s][0].push_back({t,1}) ;
        if((dp[t][0]+2)<=dp[t][1])
        {
            sum += dp[t][0] + 2 , pick[s][1].push_back({t,0}) , ++pos ;
            good = 1 ;
        }
        else
        {
            if(dp[t][0]<dp[t][1])
            {
                rd = t ;
                idx = pos ;
            }
            sum += dp[t][1] , pick[s][1].push_back({t,1}) , ++pos;
        }
    }
    if(!leaf)
    {
        if(!good)
        {
            if(rd)
            {
                pick[s][1].erase(pick[s][1].begin()+idx) ;
                pick[s][1].push_back({rd,0}) ;
                sum -= dp[rd][1] ;
                sum += dp[rd][0] + 2 ;
            }
            else
            {
                pick[s][1][0].second = 2 ;
                sum += 2 ;
            }
        }
        dp[s][1] = sum ;
    }
}

void build(int s , int c)
{
    if(c==2) c = 1 ;
    for(pair<int,int> p : pick[s][c])
    {
        build(p.first,p.second) ;
        if(p.second!=1) swap(mn[p.first],mn[s]) ;
    }
}

struct centroid_tree
{
    long long cst = 0 ;
    int N = 0 ;
    vector<int> S ;
    vector<vector<int> > adj ;
    vector<int> sub , centroid , mx , par ;
    void init(int n , vector<int> f[])
    {
        N = n ;
        adj = vector<vector<int> > (n+2) ;
        sub = vector<int> (n+2,0) ;
        mx = vector<int> (n+2,0) ;
        par = vector<int> (n+2,0) ;
        centroid = vector<int> (n+2,0) ;
        for(int i = 1 ; i <= n ; ++i)
        {
            mx[i] = i ;
            for(int j : f[i])
            {
                adj[i].push_back(j) ;
            }
        }
        find_ans() ;
    }
    void find_siz(int s , int p)
    {
        sub[s] = 1 ;
        for(int t : adj[s])
        {
            if(t==p) continue ;
            if(centroid[t]) continue ;
            find_siz(t,s) ;
            sub[s] += sub[t] ;
        }
        for(int t : adj[s])
        {
            if(t==p) continue ;
            cst += min(sub[t],N-sub[t]) ;
        }
    }
    int find_centroid(int s , int p , int n)
    {
        for(int t : adj[s])
        {
            if(t==p) continue ;
            if(centroid[t]) continue ;
            if(sub[t]>(n/2)) return find_centroid(t,s,n) ;
        }
        return s ;
    }

    void topsort(int s , int p)
    {
        for(int t : adj[s])
        {
            if(t==p) continue ;
            topsort(t,s) ;
        }
        S.push_back(s) ;
    }
    void find_ans()
    {
        find_siz(1,0) ;
        int C = find_centroid(1,0,sub[1]) ;
        topsort(C,0) ;
        reverse(S.begin(),S.end()) ;
        for(int i = 0 ; i < (N/2) ; ++i)
        {
            swap(mx[S[i]],mx[S[(i+(N/2))%N]]) ;
        }
        if((N&1) && (N>=2)) swap(mx[S[N-2]],mx[S[N-1]]) ;
    }
};

int main()
{
    int n ;
    scanf("%d",&n) ;
    for(int i = 1 ; i < n ; ++i)
    {
        int x , y ;
        scanf("%d%d",&x,&y) ;
        adj[x].push_back(y) ;
        adj[y].push_back(x) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        mn[i] = i ;
    }
    dfs(1,0) ;
    build(1,1) ;
    centroid_tree C ;
    C.init(n,adj) ;
    printf("%d %lld\n",dp[1][1],2*C.cst) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        printf("%d ",mn[i]) ;
    }
    printf("\n") ;
    for(int i = 1 ; i <= n ; ++i)
    {
        printf("%d ",C.mx[i]) ;
    }
    printf("\n") ;
    return 0 ;
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
Village.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf("%d%d",&x,&y) ;
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7248 KB Output is correct
5 Partially correct 5 ms 7252 KB Partially correct
6 Partially correct 4 ms 7328 KB Partially correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 5 ms 7348 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 5 ms 7264 KB Output is correct
12 Correct 6 ms 7252 KB Output is correct
13 Correct 4 ms 7352 KB Output is correct
14 Correct 4 ms 7252 KB Output is correct
15 Correct 4 ms 7252 KB Output is correct
16 Correct 5 ms 7352 KB Output is correct
17 Correct 4 ms 7252 KB Output is correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 12 ms 7380 KB Output is correct
3 Partially correct 6 ms 7380 KB Partially correct
4 Correct 6 ms 7484 KB Output is correct
5 Partially correct 5 ms 7484 KB Partially correct
6 Partially correct 6 ms 7508 KB Partially correct
7 Correct 5 ms 7508 KB Output is correct
8 Partially correct 5 ms 7508 KB Partially correct
9 Partially correct 5 ms 7508 KB Partially correct
10 Correct 5 ms 7484 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 5 ms 7480 KB Output is correct
13 Correct 5 ms 7484 KB Output is correct
14 Correct 7 ms 7440 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 6 ms 7508 KB Output is correct
17 Correct 7 ms 7508 KB Output is correct
18 Partially correct 5 ms 7508 KB Partially correct
19 Correct 6 ms 7484 KB Output is correct
20 Correct 6 ms 7484 KB Output is correct
21 Correct 6 ms 7508 KB Output is correct
22 Correct 6 ms 7508 KB Output is correct
23 Correct 5 ms 7484 KB Output is correct
24 Correct 6 ms 7508 KB Output is correct
25 Correct 5 ms 7380 KB Output is correct
26 Correct 7 ms 7496 KB Output is correct
27 Partially correct 5 ms 7380 KB Partially correct
28 Correct 7 ms 7508 KB Output is correct
29 Partially correct 5 ms 7484 KB Partially correct
30 Correct 5 ms 7488 KB Output is correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7248 KB Output is correct
5 Partially correct 5 ms 7252 KB Partially correct
6 Partially correct 4 ms 7328 KB Partially correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 5 ms 7348 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 5 ms 7264 KB Output is correct
12 Correct 6 ms 7252 KB Output is correct
13 Correct 4 ms 7352 KB Output is correct
14 Correct 4 ms 7252 KB Output is correct
15 Correct 4 ms 7252 KB Output is correct
16 Correct 5 ms 7352 KB Output is correct
17 Correct 4 ms 7252 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 12 ms 7380 KB Output is correct
20 Partially correct 6 ms 7380 KB Partially correct
21 Correct 6 ms 7484 KB Output is correct
22 Partially correct 5 ms 7484 KB Partially correct
23 Partially correct 6 ms 7508 KB Partially correct
24 Correct 5 ms 7508 KB Output is correct
25 Partially correct 5 ms 7508 KB Partially correct
26 Partially correct 5 ms 7508 KB Partially correct
27 Correct 5 ms 7484 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 5 ms 7480 KB Output is correct
30 Correct 5 ms 7484 KB Output is correct
31 Correct 7 ms 7440 KB Output is correct
32 Correct 5 ms 7508 KB Output is correct
33 Correct 6 ms 7508 KB Output is correct
34 Correct 7 ms 7508 KB Output is correct
35 Partially correct 5 ms 7508 KB Partially correct
36 Correct 6 ms 7484 KB Output is correct
37 Correct 6 ms 7484 KB Output is correct
38 Correct 6 ms 7508 KB Output is correct
39 Correct 6 ms 7508 KB Output is correct
40 Correct 5 ms 7484 KB Output is correct
41 Correct 6 ms 7508 KB Output is correct
42 Correct 5 ms 7380 KB Output is correct
43 Correct 7 ms 7496 KB Output is correct
44 Partially correct 5 ms 7380 KB Partially correct
45 Correct 7 ms 7508 KB Output is correct
46 Partially correct 5 ms 7484 KB Partially correct
47 Correct 5 ms 7488 KB Output is correct
48 Partially correct 137 ms 23732 KB Partially correct
49 Partially correct 131 ms 25352 KB Partially correct
50 Correct 113 ms 25416 KB Output is correct
51 Partially correct 88 ms 21504 KB Partially correct
52 Partially correct 117 ms 25164 KB Partially correct
53 Correct 110 ms 23376 KB Output is correct
54 Correct 65 ms 23240 KB Output is correct
55 Correct 142 ms 39840 KB Output is correct
56 Correct 136 ms 31736 KB Output is correct
57 Partially correct 124 ms 29540 KB Partially correct
58 Correct 130 ms 27804 KB Output is correct
59 Correct 110 ms 25304 KB Output is correct
60 Correct 82 ms 24164 KB Output is correct
61 Correct 86 ms 24396 KB Output is correct
62 Correct 92 ms 24360 KB Output is correct
63 Correct 81 ms 23368 KB Output is correct
64 Correct 90 ms 24888 KB Output is correct
65 Correct 110 ms 24824 KB Output is correct
66 Correct 76 ms 23568 KB Output is correct
67 Correct 59 ms 19892 KB Output is correct
68 Correct 97 ms 22224 KB Output is correct
69 Correct 84 ms 24976 KB Output is correct
70 Correct 84 ms 23892 KB Output is correct
71 Correct 55 ms 19524 KB Output is correct
72 Correct 63 ms 21148 KB Output is correct
73 Correct 81 ms 25056 KB Output is correct
74 Correct 86 ms 23400 KB Output is correct
75 Correct 112 ms 24624 KB Output is correct
76 Correct 107 ms 24616 KB Output is correct
77 Correct 91 ms 24740 KB Output is correct
78 Correct 65 ms 18884 KB Output is correct
79 Partially correct 68 ms 20492 KB Partially correct
80 Partially correct 113 ms 24596 KB Partially correct
81 Correct 91 ms 24908 KB Output is correct
82 Partially correct 82 ms 23760 KB Partially correct