oj.uz

Submission #919341

# Submission time Handle Problem Language Result Execution time Memory
919341 2024-01-31T15:38:34 Z imarn Mergers (JOI19_mergers) C++14
0 / 100
 189 ms 73576 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());
        if(gg[i].size()==1)ct++;
    }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 63064 KB Output is correct
2 Correct 16 ms 63032 KB Output is correct
3 Correct 19 ms 63064 KB Output is correct
4 Correct 17 ms 63072 KB Output is correct
5 Correct 16 ms 63064 KB Output is correct
6 Correct 17 ms 63064 KB Output is correct
7 Correct 18 ms 63064 KB Output is correct
8 Correct 17 ms 63036 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 17 ms 63076 KB Output is correct
12 Correct 16 ms 63064 KB Output is correct
13 Incorrect 17 ms 63072 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 63064 KB Output is correct
2 Correct 16 ms 63032 KB Output is correct
3 Correct 19 ms 63064 KB Output is correct
4 Correct 17 ms 63072 KB Output is correct
5 Correct 16 ms 63064 KB Output is correct
6 Correct 17 ms 63064 KB Output is correct
7 Correct 18 ms 63064 KB Output is correct
8 Correct 17 ms 63036 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 17 ms 63076 KB Output is correct
12 Correct 16 ms 63064 KB Output is correct
13 Incorrect 17 ms 63072 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 63064 KB Output is correct
2 Correct 16 ms 63032 KB Output is correct
3 Correct 19 ms 63064 KB Output is correct
4 Correct 17 ms 63072 KB Output is correct
5 Correct 16 ms 63064 KB Output is correct
6 Correct 17 ms 63064 KB Output is correct
7 Correct 18 ms 63064 KB Output is correct
8 Correct 17 ms 63036 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 17 ms 63076 KB Output is correct
12 Correct 16 ms 63064 KB Output is correct
13 Incorrect 17 ms 63072 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 67176 KB Output is correct
2 Correct 170 ms 73576 KB Output is correct
3 Correct 20 ms 63064 KB Output is correct
4 Correct 19 ms 63320 KB Output is correct
5 Incorrect 16 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 63064 KB Output is correct
2 Correct 16 ms 63032 KB Output is correct
3 Correct 19 ms 63064 KB Output is correct
4 Correct 17 ms 63072 KB Output is correct
5 Correct 16 ms 63064 KB Output is correct
6 Correct 17 ms 63064 KB Output is correct
7 Correct 18 ms 63064 KB Output is correct
8 Correct 17 ms 63036 KB Output is correct
9 Correct 16 ms 63064 KB Output is correct
10 Correct 16 ms 63064 KB Output is correct
11 Correct 17 ms 63076 KB Output is correct
12 Correct 16 ms 63064 KB Output is correct
13 Incorrect 17 ms 63072 KB Output isn't correct
14 Halted 0 ms 0 KB -