oj.uz

Submission #427890

# Submission time Handle Problem Language Result Execution time Memory
427890 2021-06-15T04:02:00 Z juggernaut Capital City (JOI20_capital_city) C++17
0 / 100
 3000 ms 64152 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 a[200005];
vector<int>vec;
vector<int>g[200005];
void dfs(int v,int p){
    vec.push_back(a[v]);
    for(int to:g[v])if(to!=p)dfs(to,v);
}
int sp1[200005][20];
int sp2[200005][20];
int mn[200005];
int mx[200005];
int logs[200005];
int get_min(int l,int r){
    int len=logs[r-l+1];
    return min(sp1[l][len],sp1[r-(1<<len)+1][len]);
}
int get_max(int l,int r){
    int len=logs[r-l+1];
    return max(sp2[l][len],sp2[r-(1<<len)+1][len]);
}
bool vis[200005];
int main(){
    scanf("%d%d",&n,&k);
    vec.push_back(0);
    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);
    }
    int root;
    logs[0]--;
    for(int i=1;i<=n;i++){
        logs[i]=logs[i>>1]+1;
        if(g[i].size()==1)root=i;
        scanf("%d",&a[i]);
        mn[i]=2e9;
        mx[i]=-2e9;
    }
    dfs(root,0);
    for(int i=1;i<=n;i++){
        umin(mn[vec[i]],i);
        umax(mx[vec[i]],i);
    }
    for(int i=1;i<=n;i++){
        sp1[i][0]=mn[vec[i]];
        sp2[i][0]=mx[vec[i]];
    }
    for(int j=1;j<20;j++)
    for(int i=1;i+(1<<j)-1<=n;i++){
        sp1[i][j]=min(sp1[i][j-1],sp1[i+(1<<(j-1))][j-1]);
        sp2[i][j]=max(sp2[i][j-1],sp2[i+(1<<(j-1))][j-1]);
    }
    int ans=n;
    for(int i=1;i<=n;i++){
        int l=i,r=i;
        while(get_min(l,r)!=l||get_max(l,r)!=r){
            l=get_min(l,r);
            r=get_max(l,r);
        }
        set<int>st;
        for(int j=l;j<=r;j++)
            st.insert(vec[j]);
        umin(ans,int(st.size())-1);
    }
    printf("%d",ans);
}

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:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
capital_city.cpp:60:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     dfs(root,0);
      |     ~~~^~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 4 ms 5012 KB Output is correct
7 Incorrect 4 ms 5008 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 4 ms 5012 KB Output is correct
7 Incorrect 4 ms 5008 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 64152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 4 ms 5012 KB Output is correct
7 Incorrect 4 ms 5008 KB Output isn't correct
8 Halted 0 ms 0 KB -