Submission #427890

#	Time	Username	Problem	Language	Result	Execution time	Memory
427890		juggernaut	Capital City (JOI20_capital_city)	C++17	0 / 100	3075 ms	64152 KiB

capital_city

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59