oj.uz

Submission #428265

# Submission time Handle Problem Language Result Execution time Memory
428265 2021-06-15T09:17:12 Z juggernaut Capital City (JOI20_capital_city) C++17
100 / 100
 696 ms 128096 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,k;
int tin[200005],tout[200005],timer,up[200005][18];
vector<int>g[200005],color[200005],g1[200005],g2[200005],gr[200005];

int mn[200005][18];
int mx[200005][18];
int a[200005];
void dfs(int v,int p){
    tin[v]=++timer;
    up[v][0]=p;
    mn[v][0]=::a[v];
    mx[v][0]=::a[v];
    for(int i=1;i<18;i++){
        up[v][i]=up[up[v][i-1]][i-1];
        mn[v][i]=min(mn[v][i-1],mn[up[v][i-1]][i-1]);
        mx[v][i]=max(mx[v][i-1],mx[up[v][i-1]][i-1]);
    }
    for(int to:g[v])if(to!=p)dfs(to,v);
    tout[v]=++timer;
}
bool upper(int a,int b){
    return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
int lca(int a,int b){
    if(upper(a,b))return a;
    if(upper(b,a))return b;
    for(int i=17;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i];
    return up[a][0];
}
int lca(vector<int>&vec){
    int l=vec[0];
    for(int i=1;i<(int)vec.size();i++)l=lca(l,vec[i]);
    return l;
}
unordered_map<int,bool>vs[200005];
vector<pair<int,int>>edges;
void add_edge(int a,int b){
    if(a^b){
        if(vs[a][b])return;
        vs[a][b]=true;
        edges.emplace_back(a,b);
        g1[a].push_back(b);
        gr[b].push_back(a);
    }
}
void add(int v,int a,int l){
    for(int i=17;i>=0;i--)
        if(mx[a][i]==mn[a][i])a=up[a][i];
    if(upper(a,l)&&a!=l)return;
    add_edge(v,::a[a]);
}
int cnt=0;
bool vis[200005];
int last;
int sz[200005];
int id[200005];
bool used[200005];
vector<int>order;
void run(int v){
    used[v]=true;
    for(int to:g1[v])if(!used[to])run(to);
    order.push_back(v);
}
void runner(int v){
    used[v]=true;
    sz[last]++;
    id[v]=last;
    for(int to:gr[v])if(!used[to])runner(to);
}

int dp[200005];
int goo(int v){
    if(~dp[v])return dp[v];
    dp[v]=sz[v];
    for(int to:g2[v])dp[v]+=goo(to);
    return dp[v];
}
int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        color[a[i]].push_back(i);
    }
    dfs(1,1);
    for(int i=1;i<=k;i++){
        int l=lca(color[i]);
        for(int j=0;j<(int)color[i].size();j++)add(i,color[i][j],l);
    }
    for(int i=1;i<=k;i++)if(!used[i])run(i);
    
    for(int i=1;i<=k;i++)used[i]=0;
    for(int i=1;i<=k;i++){
        int v=order[k-i];
        if(!used[v]){
            last++;
            runner(v);
        }
    }
    for(auto to:edges)if(id[to.fr]^id[to.sc]){
        g2[id[to.fr]].push_back(id[to.sc]);
    }
    int ans=k;
    for(int i=1;i<=last;i++)umin(ans,goo(i));
    printf("%d",ans-1);
}

Compilation message

capital_city.cpp: In function 'void usaco(std::string)':
capital_city.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35484 KB Output is correct
2 Correct 22 ms 35576 KB Output is correct
3 Correct 22 ms 35532 KB Output is correct
4 Correct 24 ms 35488 KB Output is correct
5 Correct 22 ms 35544 KB Output is correct
6 Correct 26 ms 35524 KB Output is correct
7 Correct 24 ms 35532 KB Output is correct
8 Correct 21 ms 35532 KB Output is correct
9 Correct 22 ms 35544 KB Output is correct
10 Correct 21 ms 35496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35484 KB Output is correct
2 Correct 22 ms 35576 KB Output is correct
3 Correct 22 ms 35532 KB Output is correct
4 Correct 24 ms 35488 KB Output is correct
5 Correct 22 ms 35544 KB Output is correct
6 Correct 26 ms 35524 KB Output is correct
7 Correct 24 ms 35532 KB Output is correct
8 Correct 21 ms 35532 KB Output is correct
9 Correct 22 ms 35544 KB Output is correct
10 Correct 21 ms 35496 KB Output is correct
11 Correct 23 ms 36180 KB Output is correct
12 Correct 22 ms 36276 KB Output is correct
13 Correct 28 ms 36300 KB Output is correct
14 Correct 28 ms 36172 KB Output is correct
15 Correct 24 ms 36300 KB Output is correct
16 Correct 26 ms 36324 KB Output is correct
17 Correct 24 ms 36196 KB Output is correct
18 Correct 23 ms 36192 KB Output is correct
19 Correct 25 ms 36224 KB Output is correct
20 Correct 24 ms 36300 KB Output is correct
21 Correct 23 ms 36300 KB Output is correct
22 Correct 23 ms 36496 KB Output is correct
23 Correct 24 ms 36428 KB Output is correct
24 Correct 25 ms 36416 KB Output is correct
25 Correct 25 ms 36376 KB Output is correct
26 Correct 23 ms 36300 KB Output is correct
27 Correct 24 ms 36368 KB Output is correct
28 Correct 24 ms 36284 KB Output is correct
29 Correct 25 ms 36308 KB Output is correct
30 Correct 25 ms 36236 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 127696 KB Output is correct
2 Correct 288 ms 127756 KB Output is correct
3 Correct 644 ms 127224 KB Output is correct
4 Correct 295 ms 127748 KB Output is correct
5 Correct 651 ms 122680 KB Output is correct
6 Correct 327 ms 127612 KB Output is correct
7 Correct 588 ms 121560 KB Output is correct
8 Correct 282 ms 123060 KB Output is correct
9 Correct 537 ms 112848 KB Output is correct
10 Correct 537 ms 110764 KB Output is correct
11 Correct 587 ms 113180 KB Output is correct
12 Correct 598 ms 115372 KB Output is correct
13 Correct 579 ms 110464 KB Output is correct
14 Correct 548 ms 115560 KB Output is correct
15 Correct 559 ms 115376 KB Output is correct
16 Correct 554 ms 111328 KB Output is correct
17 Correct 554 ms 111564 KB Output is correct
18 Correct 593 ms 112216 KB Output is correct
19 Correct 565 ms 114664 KB Output is correct
20 Correct 550 ms 116544 KB Output is correct
21 Correct 22 ms 35480 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35484 KB Output is correct
2 Correct 22 ms 35576 KB Output is correct
3 Correct 22 ms 35532 KB Output is correct
4 Correct 24 ms 35488 KB Output is correct
5 Correct 22 ms 35544 KB Output is correct
6 Correct 26 ms 35524 KB Output is correct
7 Correct 24 ms 35532 KB Output is correct
8 Correct 21 ms 35532 KB Output is correct
9 Correct 22 ms 35544 KB Output is correct
10 Correct 21 ms 35496 KB Output is correct
11 Correct 23 ms 36180 KB Output is correct
12 Correct 22 ms 36276 KB Output is correct
13 Correct 28 ms 36300 KB Output is correct
14 Correct 28 ms 36172 KB Output is correct
15 Correct 24 ms 36300 KB Output is correct
16 Correct 26 ms 36324 KB Output is correct
17 Correct 24 ms 36196 KB Output is correct
18 Correct 23 ms 36192 KB Output is correct
19 Correct 25 ms 36224 KB Output is correct
20 Correct 24 ms 36300 KB Output is correct
21 Correct 23 ms 36300 KB Output is correct
22 Correct 23 ms 36496 KB Output is correct
23 Correct 24 ms 36428 KB Output is correct
24 Correct 25 ms 36416 KB Output is correct
25 Correct 25 ms 36376 KB Output is correct
26 Correct 23 ms 36300 KB Output is correct
27 Correct 24 ms 36368 KB Output is correct
28 Correct 24 ms 36284 KB Output is correct
29 Correct 25 ms 36308 KB Output is correct
30 Correct 25 ms 36236 KB Output is correct
31 Correct 688 ms 127696 KB Output is correct
32 Correct 288 ms 127756 KB Output is correct
33 Correct 644 ms 127224 KB Output is correct
34 Correct 295 ms 127748 KB Output is correct
35 Correct 651 ms 122680 KB Output is correct
36 Correct 327 ms 127612 KB Output is correct
37 Correct 588 ms 121560 KB Output is correct
38 Correct 282 ms 123060 KB Output is correct
39 Correct 537 ms 112848 KB Output is correct
40 Correct 537 ms 110764 KB Output is correct
41 Correct 587 ms 113180 KB Output is correct
42 Correct 598 ms 115372 KB Output is correct
43 Correct 579 ms 110464 KB Output is correct
44 Correct 548 ms 115560 KB Output is correct
45 Correct 559 ms 115376 KB Output is correct
46 Correct 554 ms 111328 KB Output is correct
47 Correct 554 ms 111564 KB Output is correct
48 Correct 593 ms 112216 KB Output is correct
49 Correct 565 ms 114664 KB Output is correct
50 Correct 550 ms 116544 KB Output is correct
51 Correct 22 ms 35480 KB Output is correct
52 Correct 479 ms 102440 KB Output is correct
53 Correct 515 ms 102460 KB Output is correct
54 Correct 528 ms 102380 KB Output is correct
55 Correct 475 ms 102420 KB Output is correct
56 Correct 493 ms 102320 KB Output is correct
57 Correct 466 ms 102352 KB Output is correct
58 Correct 582 ms 110400 KB Output is correct
59 Correct 595 ms 110884 KB Output is correct
60 Correct 631 ms 114420 KB Output is correct
61 Correct 640 ms 113980 KB Output is correct
62 Correct 290 ms 128096 KB Output is correct
63 Correct 308 ms 127988 KB Output is correct
64 Correct 283 ms 124200 KB Output is correct
65 Correct 296 ms 127560 KB Output is correct
66 Correct 440 ms 106812 KB Output is correct
67 Correct 453 ms 106708 KB Output is correct
68 Correct 440 ms 106748 KB Output is correct
69 Correct 469 ms 106760 KB Output is correct
70 Correct 446 ms 106812 KB Output is correct
71 Correct 472 ms 106924 KB Output is correct
72 Correct 460 ms 106792 KB Output is correct
73 Correct 433 ms 106064 KB Output is correct
74 Correct 455 ms 106856 KB Output is correct
75 Correct 437 ms 106816 KB Output is correct
76 Correct 635 ms 120100 KB Output is correct
77 Correct 621 ms 118588 KB Output is correct
78 Correct 594 ms 111820 KB Output is correct
79 Correct 555 ms 110004 KB Output is correct
80 Correct 548 ms 115708 KB Output is correct
81 Correct 583 ms 113044 KB Output is correct
82 Correct 568 ms 113048 KB Output is correct
83 Correct 530 ms 110320 KB Output is correct
84 Correct 551 ms 115508 KB Output is correct
85 Correct 566 ms 113852 KB Output is correct
86 Correct 546 ms 109872 KB Output is correct
87 Correct 595 ms 111468 KB Output is correct
88 Correct 609 ms 111616 KB Output is correct
89 Correct 525 ms 108048 KB Output is correct
90 Correct 571 ms 107832 KB Output is correct
91 Correct 554 ms 109996 KB Output is correct
92 Correct 541 ms 108980 KB Output is correct
93 Correct 581 ms 108680 KB Output is correct
94 Correct 536 ms 108224 KB Output is correct
95 Correct 556 ms 109248 KB Output is correct
96 Correct 696 ms 108540 KB Output is correct
97 Correct 618 ms 109984 KB Output is correct