oj.uz

Submission #787280

# Submission time Handle Problem Language Result Execution time Memory
787280 2023-07-19T03:35:01 Z winter0101 Capital City (JOI20_capital_city) C++14
0 / 100
 499 ms 65288 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
vector<int>a[maxn];
int sub[maxn];
int st[maxn][18];
int dep[maxn];
int col[maxn];
int c[maxn];
vector<int>ver[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
    if (v==par)continue;
    st[v][0]=u;
    for1(i,1,17)st[v][i]=st[st[v][i-1]][i-1];
    dep[v]=dep[u]+1;
    dfs(v,u);
    sub[u]+=sub[v];
    if (a[u][0]==par||sub[a[u][0]]<sub[v]){
        swap(v,a[u][0]);
    }
}
}
int tme=0;
int h[maxn],pos[maxn],rev[maxn];
void hld(int u,int par,int head){
h[u]=head;
pos[u]=++tme;
rev[pos[u]]=u;
if (a[u][0]!=par){
    hld(a[u][0],u,head);
}
for (auto v:a[u]){
    if (v==par||v==a[u][0])continue;
    hld(v,u,v);
}
}
int lca(int u,int v){
if (u==0)return v;
if (v==0)return u;
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for1(i,0,17){
if (k>>i&1)u=st[u][i];
}
if (u==v)return u;
for2(i,17,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
    u=st[u][i];
    v=st[v][i];
}
}
return st[u][0];
}
int f[maxn];
int findset(int u){
if (f[u]<0)return u;
return f[u]=findset(f[u]);
}
void unite(int u,int v){
u=findset(u),v=findset(v);
if (u==v)return ;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
col[u]=lca(col[u],col[v]);
for (auto v1:ver[v]){
    ver[u].pb(v1);
}
vector<int>().swap(ver[v]);
f[v]=u;
}
int num[maxn],low[maxn],tim=0;
int n,k;
stack<int>scc;
struct ITgetmin{
vector<int>st;
void resz(int _n){
st.resize(4*_n+9);
}
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return ;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return n+1;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
};
pii combine(const pii &p, const pii &q){
if (p.se>q.se)return p;
else return q;
}
struct IT{
vector<pii>st;
void resz(int _n){
st.resize(4*_n+9);
}
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return ;
if (l==r){
    st[id]={l,val};
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=combine(st[id*2],st[id*2+1]);
}
pii get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return {0,0};
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return combine(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
};
ITgetmin st1;
IT st2;
void dfs(int u){
num[u]=low[u]=++tim;
scc.push(u);
//cerr<<"DFS "<<u<<'\n';
for (auto v:ver[u]){
    st1.update(1,1,n,pos[v],num[u]);
    st2.update(1,1,n,pos[v],num[u]);
}
for (auto v:ver[u]){
    int v1=v;
    while (h[v1]!=h[col[u]]){
        int l=pos[h[v1]],r=pos[v1];
        while (true){
            pii tmp=st2.get(1,1,n,l,r);
            if (tmp.se!=n+1)break;
            dfs(c[rev[tmp.fi]]);
        }
        v1=st[h[v1]][0];
    }
    int l=pos[col[u]],r=pos[v1];
    if (l>r)swap(l,r);
     while (true){
        pii tmp=st2.get(1,1,n,l,r);
        if (tmp.se!=n+1)break;
        dfs(c[rev[tmp.fi]]);
    }
}
for (auto v:ver[u]){
    int v1=v;
    while (h[v1]!=h[col[u]]){
        int l=pos[h[v1]],r=pos[v1];
        low[u]=min(low[u],st1.get(1,1,n,l,r));
        v1=st[h[v1]][0];
    }
    int l=pos[col[u]],r=pos[v1];
    if (l>r)swap(l,r);
    low[u]=min(low[u],st1.get(1,1,n,l,r));
}
if (num[u]==low[u]){
    while (scc.top()!=u){
        int v=scc.top();
        scc.pop();
        unite(u,v);
    }
    scc.pop();
    for (auto v:ver[findset(u)]){
        st1.update(1,1,n,pos[v],n+1);
    }
}
else {
    for (auto v:ver[u]){
        st1.update(1,1,n,pos[v],low[u]);
    }
}
}
int bit[maxn];
void add(int pos1,int val){
for(;pos1<=n;pos1+=(pos1-(pos1&(pos1-1))))bit[pos1]+=val;
}
int get(int pos1){
int sum=0;
for(;pos1>=1;pos1-=(pos1-(pos1&(pos1-1))))sum+=bit[pos1];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>k;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    hld(1,0,1);
    for1(i,1,n){
    cin>>c[i];
    ver[c[i]].pb(i);
    col[c[i]]=lca(col[c[i]],i);
    }
    st1.resz(n);
    for1(i,1,n){
    st1.update(1,1,n,i,n+1);
    }
    st2.resz(n);
    for1(i,1,n){
    st2.update(1,1,n,i,n+1);
    }
    for1(i,1,k)f[i]=-1;
    for1(i,1,k){
    if (!num[i]){
        dfs(i);
    }
    }
    int ans=k-1;
    for1(i,1,n)add(i,1);
    for1(i,1,k){
    if (f[i]<0){
     for (auto v:ver[i]){
        add(pos[v],-1);
     }
     int sum=0;
     for (auto v:ver[i]){
        int u=v;
        while(h[u]!=h[col[i]]){
            int l=pos[h[u]],r=pos[u];
            sum+=get(l,r);
            u=st[h[u]][0];
        }
        int l=pos[col[i]],r=pos[u];
        if (l>r)swap(l,r);
        sum+=get(l,r);
     }
     if (sum==0){
        ans=min(ans,abs(f[i])-1);
     }
     for (auto v:ver[i]){
        add(pos[v],1);
     }
    }
    }
    cout<<ans;

}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Runtime error 12 ms 19540 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Runtime error 12 ms 19540 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 64924 KB Output is correct
2 Correct 284 ms 65288 KB Output is correct
3 Correct 474 ms 64568 KB Output is correct
4 Correct 280 ms 65236 KB Output is correct
5 Correct 489 ms 61796 KB Output is correct
6 Correct 277 ms 65228 KB Output is correct
7 Correct 492 ms 61864 KB Output is correct
8 Correct 273 ms 64556 KB Output is correct
9 Correct 468 ms 60024 KB Output is correct
10 Correct 468 ms 58016 KB Output is correct
11 Correct 461 ms 60372 KB Output is correct
12 Correct 466 ms 63200 KB Output is correct
13 Correct 499 ms 57388 KB Output is correct
14 Correct 473 ms 62884 KB Output is correct
15 Correct 476 ms 63076 KB Output is correct
16 Correct 474 ms 57952 KB Output is correct
17 Correct 498 ms 58560 KB Output is correct
18 Correct 460 ms 58876 KB Output is correct
19 Correct 471 ms 62036 KB Output is correct
20 Correct 463 ms 64108 KB Output is correct
21 Runtime error 12 ms 19540 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Runtime error 12 ms 19540 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -