oj.uz

Submission #714094

# Submission time Handle Problem Language Result Execution time Memory
714094 2023-03-23T22:55:14 Z hackerbhaiya Synchronization (JOI13_synchronization) C++14
20 / 100
 2785 ms 48836 KB 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

ll n,m,q,tt=1;
vector<vector<ll> > v,dp;
vector<ll> in,out,dis;

struct node
{
    ll val;
    node()
    {
        val=0;
    }
};

vector<ll> a;
vector<node> t;

node merge(node a, node b)
{
    node ans;
    ans.val=(a.val+b.val);
    return ans;
}

void build(int id, int l, int r)
{
    if(l==r)
    {
        t[id].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid),build(id<<1|1,mid+1,r);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

void update(int id, int l, int r, int pos, ll p)
{
    if(l>pos || r<pos)
        return;
    if(l==r)
    {
        t[id].val+=p;
        return;
    }
    int mid=(l+r)/2;
    update(id<<1,l,mid,pos,p),update(id<<1|1,mid+1,r,pos,p);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

node query(int id, int l, int r, int lq, int rq)
{
    node def_val;
    if(l>rq || r<lq)
        return def_val;
    if(l>=lq && r<=rq)
        return t[id];
    int mid=(l+r)/2;
    return merge(query(id<<1,l,mid,lq,rq),query(id<<1|1,mid+1,r,lq,rq));
}

const int N=21;
int kth_ancestor(int node, int k)
{
    f(i,0,N)
    {
        if(k&1)
            node=dp[node][i];
        k>>=1;
    }
    return node;
}
 
ll find(ll a)
{
    rf(i,N-1,0)
    {
        ll node=kth_ancestor(a,i),cur=query(1,1,tt,in[node]+1,in[a]).val;
        if(!cur)
            a=node;
    }
    return a;
}

void dfs(ll cur, ll par)
{
    dp[cur][0]=par,in[cur]=tt++;
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i];
        if(node!=par)
        {
            dis[node]=1+dis[cur];
            dfs(node,cur);
        }
    }
    out[cur]=tt++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(ilu,1,z+1)
    {
        // cout<<"Case #"<<ilu<<": ";
        cin>>n>>m>>q;

        v.rz(n+1),in.rz(n+1),out.rz(n+1),dis.rz(n+1),dp.rz(n+1,vector<ll> (N));
        vector<array<ll,2> > ed;
        ed.pb({0,0});
        
        f(i,1,n)
        {
            ll l,r;
            cin>>l>>r;
            v[l].pb(r),v[r].pb(l),ed.pb({l,r});
        }

        dfs(1,1);
        f(j,1,N)
        {
            f(i,1,n+1)
                dp[i][j]=dp[dp[i][j-1]][j-1];
        }
        f(i,1,n)
        {
            if(in[ed[i][0]]>in[ed[i][1]])
                swap(ed[i][0],ed[i][1]);
        }
        a.rz(tt+1),t.rz(4*tt+69);
        f(i,2,n+1)
            a[in[i]]=1,a[out[i]]=-1;
        build(1,1,tt);

        vector<ll> last(n+1),val(n+1,1);
        vector<ll> active(n+1);
        f(i,0,m)
        {
            
            ll id;
            cin>>id;

            ll l=ed[id][0],r=ed[id][1];
            
            if(active[id])
            {
                ll x=find(r);
                val[r]=last[id]=val[x];
                update(1,1,tt,in[r],1),update(1,1,tt,out[r],-1);
                
            }
            else
            {
                ll x=find(l),y=find(r),tot=val[x]+val[y]-last[id];
                val[x]=last[id]=tot;
                update(1,1,tt,in[r],-1),update(1,1,tt,out[r],1);
                
            }
            active[id]^=1;
        }

        while(q--)
        {
            ll node;
            cin>>node;
            cout<<val[find(node)]<<"\n";
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 716 KB Output is correct
7 Correct 161 ms 4536 KB Output is correct
8 Correct 167 ms 4432 KB Output is correct
9 Correct 173 ms 4488 KB Output is correct
10 Correct 2204 ms 42376 KB Output is correct
11 Correct 2297 ms 42376 KB Output is correct
12 Correct 1591 ms 48016 KB Output is correct
13 Correct 1664 ms 42196 KB Output is correct
14 Correct 1332 ms 41812 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1441 ms 44904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 724 KB Output is correct
7 Correct 163 ms 5108 KB Output is correct
8 Correct 1974 ms 48836 KB Output is correct
9 Correct 1977 ms 48828 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1925 ms 48788 KB Output is correct
2 Incorrect 1281 ms 48076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 19 ms 724 KB Output is correct
6 Correct 200 ms 4556 KB Output is correct
7 Correct 2785 ms 43196 KB Output is correct
8 Correct 1928 ms 48816 KB Output is correct
9 Correct 2019 ms 43188 KB Output is correct
10 Correct 1764 ms 43012 KB Output is correct
11 Incorrect 1792 ms 45860 KB Output isn't correct
12 Halted 0 ms 0 KB -