oj.uz

Submission #622986

# Submission time Handle Problem Language Result Execution time Memory
622986 2022-08-04T22:40:19 Z urosk Synchronization (JOI13_synchronization) C++14
100 / 100
 888 ms 36972 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
*/
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 100005
#define lg 18
ll n,m,q;
vector<ll> g[maxn];
pll edge[maxn];
ll in[maxn];
ll t[4*maxn];
ll a[maxn];
ll c[maxn];
ll up[maxn];
ll sub[maxn];
ll st[maxn][lg];
bool tu[maxn];
ll timer = 0;
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){t[v] = x;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(2*v,tl,mid,i,x);
    else upd(2*v+1,mid+1,tr,i,x);
    t[v] = t[2*v] + t[2*v+1];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return 0;
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return sum(2*v,tl,mid,l,min(mid,r)) + sum(2*v+1,mid+1,tr,max(mid+1,l),r);
}
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = 1;
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid); init(2*v+1,mid+1,tr);
    t[v] = t[2*v] + t[2*v+1];
}
void dfs_siz(ll u,ll par){
    sub[u] = 1; st[u][0] = par;
    for(ll s : g[u]) if(s!=par) dfs_siz(s,u),sub[u]+=sub[s];
}
void dfs(ll u,ll par,ll last){
    up[u] = last;
    in[u] = ++timer;
    ll smax = 0;
    for(ll s : g[u]){
        if(s==par) continue;
        if(sub[s]>sub[smax]) smax = s;
    }
    if(smax!=0) dfs(smax,u,last);
    for(ll s : g[u]){
        if(s==par||s==smax) continue;
        dfs(s,u,s);
    }
}
ll root(ll u){
    if(sum(1,1,n,in[u],in[u])) return u;
    ll v = up[u];
    ll cur = sum(1,1,n,in[v],in[u]);
    while(!cur&&u!=1){
        if(sum(1,1,n,in[u],in[u])) return u;
        u = st[v][0]; v = up[u]; cur = sum(1,1,n,in[v],in[u]);
    }
    if(sum(1,1,n,in[u],in[u])) return u;
    ll ans = u;
    for(ll j = lg-1;j>=0;j--){
        if(in[st[ans][j]]<in[v]) continue;
        if(sum(1,1,n,in[st[ans][j]],in[u])==0) ans = st[ans][j];
    }
    return st[ans][0];
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> m >> q;
    fill(a+1,a+n+1,1);
    for(ll i = 1;i<=n-1;i++){
        ll &x = edge[i].fi; ll &y = edge[i].sc;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs_siz(1,1); dfs(1,1,1);
    init(1,1,n);
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
    while(m--){
        ll i; cin >> i;
        ll x = edge[i].fi; ll y = edge[i].sc;
        if(in[x]>in[y]) swap(x,y);
        if(tu[i]){
            a[y] = c[y] = a[root(y)];
            upd(1,1,n,in[y],1);
            tu[i] = 0;
        }else{
            a[root(x)] += a[y] - c[y];
            upd(1,1,n,in[y],0);
            tu[i] = 1;
        }
    }
    while(q--){
        ll x; cin >> x;
        cout<<a[root(x)]<<endl;
    }
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 19 ms 5524 KB Output is correct
8 Correct 19 ms 5460 KB Output is correct
9 Correct 20 ms 5460 KB Output is correct
10 Correct 300 ms 30428 KB Output is correct
11 Correct 290 ms 30436 KB Output is correct
12 Correct 635 ms 36096 KB Output is correct
13 Correct 196 ms 30220 KB Output is correct
14 Correct 196 ms 29084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 30280 KB Output is correct
2 Correct 362 ms 32168 KB Output is correct
3 Correct 257 ms 34728 KB Output is correct
4 Correct 260 ms 34716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 6 ms 3028 KB Output is correct
7 Correct 57 ms 6136 KB Output is correct
8 Correct 868 ms 36972 KB Output is correct
9 Correct 833 ms 36768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 34008 KB Output is correct
2 Correct 576 ms 35796 KB Output is correct
3 Correct 576 ms 35988 KB Output is correct
4 Correct 577 ms 35976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 27 ms 5580 KB Output is correct
7 Correct 366 ms 31236 KB Output is correct
8 Correct 820 ms 36904 KB Output is correct
9 Correct 222 ms 31284 KB Output is correct
10 Correct 517 ms 30392 KB Output is correct
11 Correct 539 ms 33712 KB Output is correct
12 Correct 535 ms 33684 KB Output is correct
13 Correct 570 ms 35960 KB Output is correct