oj.uz

Submission #547960

# Submission time Handle Problem Language Result Execution time Memory
547960 2022-04-12T04:46:24 Z Fysty Synchronization (JOI13_synchronization) C++17
100 / 100
 413 ms 23440 KB 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repk(i,m,n) for(int i=m;i<n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)
const int N=1e5+5;
vector<int> ed[N];
vector<pii> e;
int n,m,q,bit[N],tin[N],tout[N],an[20][N],ti=1;
int a[N],last[N];
bool state[N];
void upd(int x,int val)
{
    for(;x<=n;x+=x&-x) bit[x]+=val;
}
int qry(int x)
{
    int ret=0;
    for(;x;x-=x&-x) ret+=bit[x];
    return ret;
}
void dfs(int u,int p)
{
    tin[u]=ti++;
    an[0][u]=p;
    for(int v:ed[u]) if(v!=p) dfs(v,u);
    tout[u]=ti;
}
int croot(int x)
{
    int r=x,tot=qry(tin[x]);
    for(int i=18;i>=0;i--)
    {
        if(an[i][r]==0) continue;
        if(qry(tin[an[i][r]])==tot) r=an[i][r];
    }
    return r;
}
signed main()
{
    MottoHayaku
    cin>>n>>m>>q;
    rep(i,n-1)
    {
        int u,v;
        cin>>u>>v;
        ed[u].pb(v);
        ed[v].pb(u);
        e.pb({u,v});
    }
    dfs(1,0);
    rep1(i,18) rep1(j,n) an[i][j]=an[i-1][an[i-1][j]];
    rep1(i,n)
    {
        a[i]=1;
        upd(tin[i],-1);
        upd(tout[i],1);
    }
    rep(i,m)
    {
        int id;
        cin>>id;
        id--;
        int u=e[id].F,v=e[id].S;
        if(an[0][u]==v) swap(u,v);
        if(state[id])
        {
            a[v]=last[v]=a[croot(u)];
            upd(tin[v],-1);
            upd(tout[v],1);
        }
        else
        {
            a[croot(u)]+=a[v]-last[v];
            upd(tin[v],1);
            upd(tout[v],-1);
        }
        state[id]=!state[id];
    }
    while(q--)
    {
        int u;
        cin>>u;
        cout<<a[croot(u)]<<"\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2732 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 12 ms 4308 KB Output is correct
8 Correct 11 ms 4308 KB Output is correct
9 Correct 12 ms 4352 KB Output is correct
10 Correct 187 ms 18504 KB Output is correct
11 Correct 182 ms 18412 KB Output is correct
12 Correct 330 ms 23016 KB Output is correct
13 Correct 70 ms 18492 KB Output is correct
14 Correct 113 ms 17444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 18284 KB Output is correct
2 Correct 76 ms 20200 KB Output is correct
3 Correct 98 ms 22128 KB Output is correct
4 Correct 103 ms 22108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 19 ms 4848 KB Output is correct
8 Correct 386 ms 23412 KB Output is correct
9 Correct 389 ms 23400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 20896 KB Output is correct
2 Correct 134 ms 23160 KB Output is correct
3 Correct 134 ms 23224 KB Output is correct
4 Correct 136 ms 23356 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 16 ms 4400 KB Output is correct
7 Correct 234 ms 18752 KB Output is correct
8 Correct 404 ms 23440 KB Output is correct
9 Correct 99 ms 19400 KB Output is correct
10 Correct 138 ms 18752 KB Output is correct
11 Correct 101 ms 21636 KB Output is correct
12 Correct 100 ms 21496 KB Output is correct
13 Correct 133 ms 23352 KB Output is correct