Submission #919350

#	Time	Username	Problem	Language	Result	Execution time	Memory
919350		imarn	Mergers (JOI19_mergers)	C++14	24 / 100	466 ms	74268 KiB

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;
}

Compilation message (stderr)

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);
      |                     ~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 24
• Subtask 3: 14 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30