oj.uz

Submission #919340

# Submission time Handle Problem Language Result Execution time Memory
919340 2024-01-31T15:35:57 Z imarn Mergers (JOI19_mergers) C++14
0 / 100
 209 ms 73560 KB 
#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;
void push(int i,int l,int r){
    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,cur,id[head[x]],id[x],z);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    upd(1,1,cur,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,cur,id[head[x]],id[x]),res);
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    res=min(res,qr(1,1,cur,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 n,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<=n;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);
        for(int j=0;j<gr[i].size();j++)pos[gr[i][j]]=res;
        cp++;
    }
    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());
        ct+=(gg[i].size()==1);
    }cout<<(ct+1)/2;
}

Compilation message

mergers.cpp: In function 'void dfssz(int, int, int)':
mergers.cpp:59:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |         if(v==p)continue;dfssz(v,u,l+1);
      |         ^~
mergers.cpp:59:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |         if(v==p)continue;dfssz(v,u,l+1);
      |                          ^~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
      |                     ~^~~~~~~~~~~~~
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++)update(top,gr[i][j],res);
      |                     ~^~~~~~~~~~~~~
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++)pos[gr[i][j]]=res;
      |                     ~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 63056 KB Output is correct
2 Correct 16 ms 63064 KB Output is correct
3 Correct 17 ms 63064 KB Output is correct
4 Correct 16 ms 63072 KB Output is correct
5 Correct 17 ms 63320 KB Output is correct
6 Correct 18 ms 63068 KB Output is correct
7 Correct 16 ms 63064 KB Output is correct
8 Correct 18 ms 63064 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 16 ms 63076 KB Output is correct
12 Correct 18 ms 63064 KB Output is correct
13 Incorrect 17 ms 63052 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 63056 KB Output is correct
2 Correct 16 ms 63064 KB Output is correct
3 Correct 17 ms 63064 KB Output is correct
4 Correct 16 ms 63072 KB Output is correct
5 Correct 17 ms 63320 KB Output is correct
6 Correct 18 ms 63068 KB Output is correct
7 Correct 16 ms 63064 KB Output is correct
8 Correct 18 ms 63064 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 16 ms 63076 KB Output is correct
12 Correct 18 ms 63064 KB Output is correct
13 Incorrect 17 ms 63052 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 63056 KB Output is correct
2 Correct 16 ms 63064 KB Output is correct
3 Correct 17 ms 63064 KB Output is correct
4 Correct 16 ms 63072 KB Output is correct
5 Correct 17 ms 63320 KB Output is correct
6 Correct 18 ms 63068 KB Output is correct
7 Correct 16 ms 63064 KB Output is correct
8 Correct 18 ms 63064 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 16 ms 63076 KB Output is correct
12 Correct 18 ms 63064 KB Output is correct
13 Incorrect 17 ms 63052 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 67276 KB Output is correct
2 Correct 155 ms 73560 KB Output is correct
3 Correct 19 ms 63224 KB Output is correct
4 Correct 22 ms 63156 KB Output is correct
5 Incorrect 17 ms 63064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 63056 KB Output is correct
2 Correct 16 ms 63064 KB Output is correct
3 Correct 17 ms 63064 KB Output is correct
4 Correct 16 ms 63072 KB Output is correct
5 Correct 17 ms 63320 KB Output is correct
6 Correct 18 ms 63068 KB Output is correct
7 Correct 16 ms 63064 KB Output is correct
8 Correct 18 ms 63064 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 16 ms 63076 KB Output is correct
12 Correct 18 ms 63064 KB Output is correct
13 Incorrect 17 ms 63052 KB Output isn't correct
14 Halted 0 ms 0 KB -