Submission #919349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919349	2024-01-31T15:56:19 Z	imarn	Mergers (JOI19_mergers)	C++14	Compilation error	0 ms	0 KB

mergers

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=5e5+5;
vector<int>g[N],gg[N];
int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
void push(int i,int l,int r){
    if(lz[i]==1e9)return;
    t[i]=min(t[i],lz[i]);
    if(l<r){
        lz[2*i]=min(lz[2*i],lz[i]);
        lz[2*i+1]=min(lz[2*i+1],lz[i]);
    }lz[i]=1e9;
}
void upd(int i,int l,int r,int tl,int tr,int id){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]=min(lz[i],id);push(i,l,r);
        return;
    }int m=(l+r)>>1;
    upd(2*i,l,m,tl,tr,id);upd(2*i+1,m+1,r,tl,tr,id);
    t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
    push(i,l,r);
    if(r<tl||l>tr)return 1e9;
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
void update(int x,int y,int z){
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        upd(1,1,n,id[head[x]],id[x],z);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    upd(1,1,n,id[x],id[y],z);
}
int query(int x,int y,int res=1e9){
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        res=min(qr(1,1,n,id[head[x]],id[x]),res);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    res=min(res,qr(1,1,n,id[x],id[y]));return res;
}
void dfssz(int u,int p,int l){
    sz[u]=1;dep[u]=l;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;dfssz(v,u,l+1);
        sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cur;
    int hc=-1,hv=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(sz[v]>hc)hv=v,hc=sz[v];
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}vector<int>gr[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int k;cin>>n>>k;
    for(int i=0;i<4*N;i++)t[i]=lz[i]=1e9;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
    }dfssz(1,1,0);hld(1,1,1);
    for(int i=1,x;i<=n;i++)cin>>x,gr[x].pb(i);
    for(int i=1;i<=k;i++){
        if(gr[i].empty())continue;
        int top=gr[i][0];int res=cp;
        for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
        for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
        cp++;
    }for(int i=1;i<=n;i++)pos[i]=qr(1,1,n,id[i],id[i]);
    for(int i=1;i<=n;i++){
        for(auto v:g[i]){
            if(pos[v]==pos[i])continue;
            gg[pos[v]].pb(pos[i]);
            gg[pos[i]].pb(pos[v]);
        }
    }int ct=0;
    for(int i=1;i<=n;i++){
        if(gg[i].empty())continue;
        sort(gg[i].begin(),gg[i].end());
        gg[i].erase(unique(gg[i].begin(),gg[i].end()),gg[i].end());
        if(gg[i].size()==1)ct++;
    }cout<<(ct+1)/2;
}
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=5e5+5;
vector<int>g[N],gg[N];
int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
void push(int i,int l,int r){
    if(lz[i]==1e9)return;
    t[i]=min(t[i],lz[i]);
    if(l<r){
        lz[2*i]=min(lz[2*i],lz[i]);
        lz[2*i+1]=min(lz[2*i+1],lz[i]);
    }lz[i]=1e9;
}
void upd(int i,int l,int r,int tl,int tr,int id){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]=min(lz[i],id);push(i,l,r);
        return;
    }int m=(l+r)>>1;
    upd(2*i,l,m,tl,tr,id);upd(2*i+1,m+1,r,tl,tr,id);
    t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
    push(i,l,r);
    if(r<tl||l>tr)return 1e9;
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
void update(int x,int y,int z){
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        upd(1,1,n,id[head[x]],id[x],z);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    upd(1,1,n,id[x],id[y],z);
}
int query(int x,int y,int res=1e9){
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        res=min(qr(1,1,n,id[head[x]],id[x]),res);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    res=min(res,qr(1,1,n,id[x],id[y]));return res;
}
void dfssz(int u,int p,int l){
    sz[u]=1;dep[u]=l;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;dfssz(v,u,l+1);
        sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cur;
    int hc=-1,hv=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(sz[v]>hc)hv=v,hc=sz[v];
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}vector<int>gr[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int k;cin>>n>>k;
    for(int i=0;i<4*N;i++)t[i]=lz[i]=1e9;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
    }dfssz(1,1,0);hld(1,1,1);
    for(int i=1,x;i<=n;i++)cin>>x,gr[x].pb(i);
    for(int i=1;i<=k;i++){
        if(gr[i].empty())continue;
        int top=gr[i][0];int res=cp;
        for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
        for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
        cp++;
    }for(int i=1;i<=n;i++)pos[i]=qr(1,1,n,id[i],id[i]);
    for(int i=1;i<=n;i++){
        for(auto v:g[i]){
            if(pos[v]==pos[i])continue;
            gg[pos[v]].pb(pos[i]);
            gg[pos[i]].pb(pos[v]);
        }
    }int ct=0;
    for(int i=1;i<=n;i++){
        if(gg[i].empty())continue;
        sort(gg[i].begin(),gg[i].end());
        gg[i].erase(unique(gg[i].begin(),gg[i].end()),gg[i].end());
        if(gg[i].size()==1)ct++;
    }cout<<(ct+1)/2;
}

Compilation message

mergers.cpp: In function 'void dfssz(int, int, int)':
mergers.cpp:60:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   60 |         if(v==p)continue;dfssz(v,u,l+1);
      |         ^~
mergers.cpp:60:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   60 |         if(v==p)continue;dfssz(v,u,l+1);
      |                          ^~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
      |                     ~^~~~~~~~~~~~~
mergers.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
      |                     ~^~~~~~~~~~~~~
mergers.cpp: At global scope:
mergers.cpp:118:11: error: redefinition of 'const int N'
  118 | const int N=5e5+5;
      |           ^
mergers.cpp:13:11: note: 'const int N' previously defined here
   13 | const int N=5e5+5;
      |           ^
mergers.cpp:119:12: error: redefinition of 'std::vector<int> g [500005]'
  119 | vector<int>g[N],gg[N];
      |            ^
mergers.cpp:14:12: note: 'std::vector<int> g [500005]' previously declared here
   14 | vector<int>g[N],gg[N];
      |            ^
mergers.cpp:119:17: error: redefinition of 'std::vector<int> gg [500005]'
  119 | vector<int>g[N],gg[N];
      |                 ^~
mergers.cpp:14:17: note: 'std::vector<int> gg [500005]' previously declared here
   14 | vector<int>g[N],gg[N];
      |                 ^~
mergers.cpp:120:5: error: redefinition of 'int sz [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |     ^~
mergers.cpp:15:5: note: 'int sz [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |     ^~
mergers.cpp:120:11: error: redefinition of 'int id [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |           ^~
mergers.cpp:15:11: note: 'int id [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |           ^~
mergers.cpp:120:17: error: redefinition of 'int pr [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                 ^~
mergers.cpp:15:17: note: 'int pr [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                 ^~
mergers.cpp:120:23: error: redefinition of 'int head [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                       ^~~~
mergers.cpp:15:23: note: 'int head [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                       ^~~~
mergers.cpp:120:31: error: redefinition of 'int dep [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                               ^~~
mergers.cpp:15:31: note: 'int dep [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                               ^~~
mergers.cpp:120:38: error: redefinition of 'int cur'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                      ^~~
mergers.cpp:15:38: note: 'int cur' previously defined here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                      ^~~
mergers.cpp:120:44: error: redefinition of 'int t [2000020]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                            ^
mergers.cpp:15:44: note: 'int t [2000020]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                            ^
mergers.cpp:120:51: error: redefinition of 'int lz [2000020]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                   ^~
mergers.cpp:15:51: note: 'int lz [2000020]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                   ^~
mergers.cpp:120:59: error: redefinition of 'int pos [500005]'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                           ^~~
mergers.cpp:15:59: note: 'int pos [500005]' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                           ^~~
mergers.cpp:120:66: error: redefinition of 'int cp'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                                  ^~
mergers.cpp:15:66: note: 'int cp' previously defined here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                                  ^~
mergers.cpp:120:71: error: redefinition of 'int n'
  120 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                                       ^
mergers.cpp:15:71: note: 'int n' previously declared here
   15 | int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
      |                                                                       ^
mergers.cpp:121:6: error: redefinition of 'void push(int, int, int)'
  121 | void push(int i,int l,int r){
      |      ^~~~
mergers.cpp:16:6: note: 'void push(int, int, int)' previously defined here
   16 | void push(int i,int l,int r){
      |      ^~~~
mergers.cpp:129:6: error: redefinition of 'void upd(int, int, int, int, int, int)'
  129 | void upd(int i,int l,int r,int tl,int tr,int id){
      |      ^~~
mergers.cpp:24:6: note: 'void upd(int, int, int, int, int, int)' previously defined here
   24 | void upd(int i,int l,int r,int tl,int tr,int id){
      |      ^~~
mergers.cpp:139:5: error: redefinition of 'int qr(int, int, int, int, int)'
  139 | int qr(int i,int l,int r,int tl,int tr){
      |     ^~
mergers.cpp:34:5: note: 'int qr(int, int, int, int, int)' previously defined here
   34 | int qr(int i,int l,int r,int tl,int tr){
      |     ^~
mergers.cpp:146:6: error: redefinition of 'void update(int, int, int)'
  146 | void update(int x,int y,int z){
      |      ^~~~~~
mergers.cpp:41:6: note: 'void update(int, int, int)' previously defined here
   41 | void update(int x,int y,int z){
      |      ^~~~~~
mergers.cpp:154:5: error: redefinition of 'int query(int, int, int)'
  154 | int query(int x,int y,int res=1e9){
      |     ^~~~~
mergers.cpp:49:5: note: 'int query(int, int, int)' previously defined here
   49 | int query(int x,int y,int res=1e9){
      |     ^~~~~
mergers.cpp:162:6: error: redefinition of 'void dfssz(int, int, int)'
  162 | void dfssz(int u,int p,int l){
      |      ^~~~~
mergers.cpp:57:6: note: 'void dfssz(int, int, int)' previously defined here
   57 | void dfssz(int u,int p,int l){
      |      ^~~~~
mergers.cpp: In function 'void dfssz(int, int, int)':
mergers.cpp:165:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  165 |         if(v==p)continue;dfssz(v,u,l+1);
      |         ^~
mergers.cpp:165:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  165 |         if(v==p)continue;dfssz(v,u,l+1);
      |                          ^~~~~
mergers.cpp: At global scope:
mergers.cpp:169:6: error: redefinition of 'void hld(int, int, int)'
  169 | void hld(int u,int p,int tp){
      |      ^~~
mergers.cpp:64:6: note: 'void hld(int, int, int)' previously defined here
   64 | void hld(int u,int p,int tp){
      |      ^~~
mergers.cpp:181:13: error: redefinition of 'std::vector<int> gr [500005]'
  181 | }vector<int>gr[N];
      |             ^~
mergers.cpp:76:13: note: 'std::vector<int> gr [500005]' previously declared here
   76 | }vector<int>gr[N];
      |             ^~
mergers.cpp:182:5: error: redefinition of 'int main()'
  182 | int main(){
      |     ^~~~
mergers.cpp:77:5: note: 'int main()' previously defined here
   77 | int main(){
      |     ^~~~
mergers.cpp: In function 'int main()':
mergers.cpp:193:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
      |                     ~^~~~~~~~~~~~~
mergers.cpp:194:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
      |                     ~^~~~~~~~~~~~~