oj.uz

Submission #428202

# Submission time Handle Problem Language Result Execution time Memory
428202 2021-06-15T08:49:25 Z juggernaut Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 92580 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 a[200005];
void dfs(int v,int p){
    tin[v]=++timer;
    up[v][0]=p;
    for(int i=1;i<18;i++)up[v][i]=up[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){
    while(a!=l){
        a=up[a][0];
        add_edge(v,::a[a]);
        if(v^::a[a])break;
    }
}
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:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30784 KB Output is correct
2 Correct 19 ms 30780 KB Output is correct
3 Correct 19 ms 30844 KB Output is correct
4 Correct 19 ms 30860 KB Output is correct
5 Correct 19 ms 30872 KB Output is correct
6 Correct 18 ms 30884 KB Output is correct
7 Correct 19 ms 30812 KB Output is correct
8 Correct 19 ms 30828 KB Output is correct
9 Correct 19 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 19 ms 30784 KB Output is correct
2 Correct 19 ms 30780 KB Output is correct
3 Correct 19 ms 30844 KB Output is correct
4 Correct 19 ms 30860 KB Output is correct
5 Correct 19 ms 30872 KB Output is correct
6 Correct 18 ms 30884 KB Output is correct
7 Correct 19 ms 30812 KB Output is correct
8 Correct 19 ms 30828 KB Output is correct
9 Correct 19 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 20 ms 31152 KB Output is correct
12 Correct 20 ms 31180 KB Output is correct
13 Correct 20 ms 31180 KB Output is correct
14 Correct 20 ms 31156 KB Output is correct
15 Correct 21 ms 31300 KB Output is correct
16 Correct 24 ms 31388 KB Output is correct
17 Correct 28 ms 31232 KB Output is correct
18 Correct 22 ms 31304 KB Output is correct
19 Correct 25 ms 31256 KB Output is correct
20 Correct 22 ms 31180 KB Output is correct
21 Correct 24 ms 31228 KB Output is correct
22 Correct 24 ms 31468 KB Output is correct
23 Correct 22 ms 31336 KB Output is correct
24 Correct 23 ms 31304 KB Output is correct
25 Correct 24 ms 31308 KB Output is correct
26 Correct 26 ms 31344 KB Output is correct
27 Correct 20 ms 31240 KB Output is correct
28 Correct 21 ms 31308 KB Output is correct
29 Correct 25 ms 31192 KB Output is correct
30 Correct 23 ms 31308 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 88976 KB Output is correct
2 Correct 228 ms 92464 KB Output is correct
3 Correct 512 ms 91948 KB Output is correct
4 Correct 223 ms 92580 KB Output is correct
5 Execution timed out 3062 ms 70948 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30784 KB Output is correct
2 Correct 19 ms 30780 KB Output is correct
3 Correct 19 ms 30844 KB Output is correct
4 Correct 19 ms 30860 KB Output is correct
5 Correct 19 ms 30872 KB Output is correct
6 Correct 18 ms 30884 KB Output is correct
7 Correct 19 ms 30812 KB Output is correct
8 Correct 19 ms 30828 KB Output is correct
9 Correct 19 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 20 ms 31152 KB Output is correct
12 Correct 20 ms 31180 KB Output is correct
13 Correct 20 ms 31180 KB Output is correct
14 Correct 20 ms 31156 KB Output is correct
15 Correct 21 ms 31300 KB Output is correct
16 Correct 24 ms 31388 KB Output is correct
17 Correct 28 ms 31232 KB Output is correct
18 Correct 22 ms 31304 KB Output is correct
19 Correct 25 ms 31256 KB Output is correct
20 Correct 22 ms 31180 KB Output is correct
21 Correct 24 ms 31228 KB Output is correct
22 Correct 24 ms 31468 KB Output is correct
23 Correct 22 ms 31336 KB Output is correct
24 Correct 23 ms 31304 KB Output is correct
25 Correct 24 ms 31308 KB Output is correct
26 Correct 26 ms 31344 KB Output is correct
27 Correct 20 ms 31240 KB Output is correct
28 Correct 21 ms 31308 KB Output is correct
29 Correct 25 ms 31192 KB Output is correct
30 Correct 23 ms 31308 KB Output is correct
31 Correct 504 ms 88976 KB Output is correct
32 Correct 228 ms 92464 KB Output is correct
33 Correct 512 ms 91948 KB Output is correct
34 Correct 223 ms 92580 KB Output is correct
35 Execution timed out 3062 ms 70948 KB Time limit exceeded
36 Halted 0 ms 0 KB -