oj.uz

Submission #428252

# Submission time Handle Problem Language Result Execution time Memory
428252 2021-06-15T09:06:37 Z juggernaut Capital City (JOI20_capital_city) C++17
100 / 100
 684 ms 123804 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];

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);
    }
}
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 low[200005],_up[200005],tt,last;
int sz[200005];
stack<int>ss;
int id[200005];
bool used[200005];
void run(int u,int p=-1){
    low[u]=_up[u]=tt++;
    used[u]=1;
    ss.push(u);
    for(auto x:g1[u])
        if(used[x] && !id[x])umin(low[u],_up[x]);
        else if(!id[x]) run(x,u),umin(low[u],low[x]);
    if(low[u] == _up[u]){
        int cur; ++last;
        do{
            cur=ss.top();ss.pop();
            id[cur]=last;
            sz[last]++;
        }while(cur != u);
    }
}
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(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:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30796 KB Output is correct
2 Correct 18 ms 30904 KB Output is correct
3 Correct 18 ms 30796 KB Output is correct
4 Correct 20 ms 30876 KB Output is correct
5 Correct 20 ms 30836 KB Output is correct
6 Correct 19 ms 30852 KB Output is correct
7 Correct 18 ms 30912 KB Output is correct
8 Correct 18 ms 30840 KB Output is correct
9 Correct 23 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30796 KB Output is correct
2 Correct 18 ms 30904 KB Output is correct
3 Correct 18 ms 30796 KB Output is correct
4 Correct 20 ms 30876 KB Output is correct
5 Correct 20 ms 30836 KB Output is correct
6 Correct 19 ms 30852 KB Output is correct
7 Correct 18 ms 30912 KB Output is correct
8 Correct 18 ms 30840 KB Output is correct
9 Correct 23 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 23 ms 31524 KB Output is correct
12 Correct 22 ms 31464 KB Output is correct
13 Correct 21 ms 31436 KB Output is correct
14 Correct 24 ms 31420 KB Output is correct
15 Correct 21 ms 31632 KB Output is correct
16 Correct 24 ms 31668 KB Output is correct
17 Correct 23 ms 31552 KB Output is correct
18 Correct 22 ms 31520 KB Output is correct
19 Correct 22 ms 31604 KB Output is correct
20 Correct 23 ms 31504 KB Output is correct
21 Correct 23 ms 31564 KB Output is correct
22 Correct 22 ms 31768 KB Output is correct
23 Correct 25 ms 31724 KB Output is correct
24 Correct 22 ms 31692 KB Output is correct
25 Correct 23 ms 31644 KB Output is correct
26 Correct 25 ms 31552 KB Output is correct
27 Correct 25 ms 31588 KB Output is correct
28 Correct 22 ms 31612 KB Output is correct
29 Correct 22 ms 31532 KB Output is correct
30 Correct 23 ms 31600 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 119660 KB Output is correct
2 Correct 311 ms 120104 KB Output is correct
3 Correct 617 ms 119532 KB Output is correct
4 Correct 291 ms 120124 KB Output is correct
5 Correct 684 ms 115248 KB Output is correct
6 Correct 292 ms 123432 KB Output is correct
7 Correct 596 ms 117740 KB Output is correct
8 Correct 278 ms 119376 KB Output is correct
9 Correct 534 ms 109848 KB Output is correct
10 Correct 535 ms 107768 KB Output is correct
11 Correct 530 ms 110244 KB Output is correct
12 Correct 531 ms 112440 KB Output is correct
13 Correct 532 ms 107312 KB Output is correct
14 Correct 566 ms 112684 KB Output is correct
15 Correct 556 ms 112336 KB Output is correct
16 Correct 525 ms 108300 KB Output is correct
17 Correct 568 ms 108608 KB Output is correct
18 Correct 502 ms 109192 KB Output is correct
19 Correct 533 ms 111672 KB Output is correct
20 Correct 578 ms 113488 KB Output is correct
21 Correct 20 ms 30856 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30796 KB Output is correct
2 Correct 18 ms 30904 KB Output is correct
3 Correct 18 ms 30796 KB Output is correct
4 Correct 20 ms 30876 KB Output is correct
5 Correct 20 ms 30836 KB Output is correct
6 Correct 19 ms 30852 KB Output is correct
7 Correct 18 ms 30912 KB Output is correct
8 Correct 18 ms 30840 KB Output is correct
9 Correct 23 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 23 ms 31524 KB Output is correct
12 Correct 22 ms 31464 KB Output is correct
13 Correct 21 ms 31436 KB Output is correct
14 Correct 24 ms 31420 KB Output is correct
15 Correct 21 ms 31632 KB Output is correct
16 Correct 24 ms 31668 KB Output is correct
17 Correct 23 ms 31552 KB Output is correct
18 Correct 22 ms 31520 KB Output is correct
19 Correct 22 ms 31604 KB Output is correct
20 Correct 23 ms 31504 KB Output is correct
21 Correct 23 ms 31564 KB Output is correct
22 Correct 22 ms 31768 KB Output is correct
23 Correct 25 ms 31724 KB Output is correct
24 Correct 22 ms 31692 KB Output is correct
25 Correct 23 ms 31644 KB Output is correct
26 Correct 25 ms 31552 KB Output is correct
27 Correct 25 ms 31588 KB Output is correct
28 Correct 22 ms 31612 KB Output is correct
29 Correct 22 ms 31532 KB Output is correct
30 Correct 23 ms 31600 KB Output is correct
31 Correct 647 ms 119660 KB Output is correct
32 Correct 311 ms 120104 KB Output is correct
33 Correct 617 ms 119532 KB Output is correct
34 Correct 291 ms 120124 KB Output is correct
35 Correct 684 ms 115248 KB Output is correct
36 Correct 292 ms 123432 KB Output is correct
37 Correct 596 ms 117740 KB Output is correct
38 Correct 278 ms 119376 KB Output is correct
39 Correct 534 ms 109848 KB Output is correct
40 Correct 535 ms 107768 KB Output is correct
41 Correct 530 ms 110244 KB Output is correct
42 Correct 531 ms 112440 KB Output is correct
43 Correct 532 ms 107312 KB Output is correct
44 Correct 566 ms 112684 KB Output is correct
45 Correct 556 ms 112336 KB Output is correct
46 Correct 525 ms 108300 KB Output is correct
47 Correct 568 ms 108608 KB Output is correct
48 Correct 502 ms 109192 KB Output is correct
49 Correct 533 ms 111672 KB Output is correct
50 Correct 578 ms 113488 KB Output is correct
51 Correct 20 ms 30856 KB Output is correct
52 Correct 436 ms 99976 KB Output is correct
53 Correct 459 ms 99824 KB Output is correct
54 Correct 460 ms 99888 KB Output is correct
55 Correct 502 ms 99844 KB Output is correct
56 Correct 488 ms 99788 KB Output is correct
57 Correct 435 ms 99876 KB Output is correct
58 Correct 572 ms 106912 KB Output is correct
59 Correct 536 ms 107500 KB Output is correct
60 Correct 674 ms 111832 KB Output is correct
61 Correct 607 ms 111620 KB Output is correct
62 Correct 279 ms 123756 KB Output is correct
63 Correct 277 ms 123804 KB Output is correct
64 Correct 294 ms 120424 KB Output is correct
65 Correct 280 ms 123432 KB Output is correct
66 Correct 475 ms 105400 KB Output is correct
67 Correct 466 ms 105356 KB Output is correct
68 Correct 465 ms 105460 KB Output is correct
69 Correct 515 ms 105532 KB Output is correct
70 Correct 451 ms 105360 KB Output is correct
71 Correct 473 ms 105388 KB Output is correct
72 Correct 480 ms 105320 KB Output is correct
73 Correct 433 ms 104636 KB Output is correct
74 Correct 434 ms 105360 KB Output is correct
75 Correct 431 ms 105456 KB Output is correct
76 Correct 570 ms 115988 KB Output is correct
77 Correct 605 ms 114284 KB Output is correct
78 Correct 521 ms 108736 KB Output is correct
79 Correct 531 ms 107024 KB Output is correct
80 Correct 510 ms 112792 KB Output is correct
81 Correct 509 ms 110132 KB Output is correct
82 Correct 550 ms 110020 KB Output is correct
83 Correct 513 ms 107388 KB Output is correct
84 Correct 539 ms 112488 KB Output is correct
85 Correct 538 ms 110928 KB Output is correct
86 Correct 512 ms 106932 KB Output is correct
87 Correct 524 ms 108644 KB Output is correct
88 Correct 536 ms 109240 KB Output is correct
89 Correct 522 ms 105908 KB Output is correct
90 Correct 564 ms 105596 KB Output is correct
91 Correct 556 ms 107828 KB Output is correct
92 Correct 539 ms 106676 KB Output is correct
93 Correct 541 ms 106460 KB Output is correct
94 Correct 554 ms 105760 KB Output is correct
95 Correct 540 ms 106936 KB Output is correct
96 Correct 541 ms 106308 KB Output is correct
97 Correct 541 ms 107704 KB Output is correct