oj.uz

Submission #770352

# Submission time Handle Problem Language Result Execution time Memory
770352 2023-07-01T05:56:49 Z bachhoangxuan Synchronization (JOI13_synchronization) C++17
100 / 100
 355 ms 62904 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=18;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;
namespace BIT{
    int n;
    vector<int> bit;
    void init(int N){
        n=N;
        bit.assign(n+1,0);
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
    void update(int x,int val){
        for(int i=x;i<=n;i+=(i&(-i))) bit[i]+=val;
    }
    void update_range(int l,int r,int val){
        update(l,val);update(r+1,-val);
    }
}
void solve(){
    int n,m,q;cin >> n >> m >> q;
    vector<vector<int>> edge(n+1),par(n+1,vector<int>(maxl,0));
    vector<pii> e(n);
    vector<int> res(n+1,1),dep(n+1,0),L(n+1),R(n+1);
    vector<int> cur(n,0),use(n,0);
    int pos=0;
    for(int i=1;i<n;i++){
        int u,v;cin >> u >> v;e[i]={u,v};
        edge[u].push_back(v);edge[v].push_back(u);
    }
    function<void(int,int)> dfs = [&](int u,int p){
        dep[u]=dep[p]+1;par[u][0]=p;L[u]=++pos;
        for(int i=1;i<maxl;i++) par[u][i]=par[par[u][i-1]][i-1];
        for(int v:edge[u]){
            if(v==p) continue;
            dfs(v,u);
        }
        R[u]=pos;
    };
    dfs(1,0);
    BIT::init(n);
    auto jmp = [=](int u){
        for(int i=maxl-1;i>=0;i--){
            int p=par[u][i];
            if(p==0) continue;
            else if(dep[u]-dep[p]==BIT::query(L[u])-BIT::query(L[p])) u=p;
        }
        return u;
    };
    for(int i=1;i<=m;i++){
        int id;cin >> id;
        auto [u,v]=e[id];
        if(u!=par[v][0]) swap(u,v);
        int p=jmp(u);
        if(use[id]){
            res[v]=cur[id]=res[p];
            BIT::update_range(L[v],R[v],-1);
        }
        else{
            res[p]+=res[v]-cur[id];
            BIT::update_range(L[v],R[v],1);
        }
        use[id]^=1;
    }
    for(int i=1;i<=q;i++){
        int u;cin >> u;
        //cout << u << ' ' << jmp(u) << '\n';
        cout << res[jmp(u)] << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

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 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 808 KB Output is correct
7 Correct 11 ms 5568 KB Output is correct
8 Correct 11 ms 5564 KB Output is correct
9 Correct 12 ms 5588 KB Output is correct
10 Correct 265 ms 53344 KB Output is correct
11 Correct 240 ms 53360 KB Output is correct
12 Correct 276 ms 62120 KB Output is correct
13 Correct 118 ms 53132 KB Output is correct
14 Correct 168 ms 52788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 57432 KB Output is correct
2 Correct 101 ms 56736 KB Output is correct
3 Correct 143 ms 61556 KB Output is correct
4 Correct 135 ms 61500 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 19 ms 6532 KB Output is correct
8 Correct 326 ms 62904 KB Output is correct
9 Correct 320 ms 62888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 62904 KB Output is correct
2 Correct 180 ms 62248 KB Output is correct
3 Correct 174 ms 62664 KB Output is correct
4 Correct 216 ms 62648 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 14 ms 5760 KB Output is correct
7 Correct 272 ms 54112 KB Output is correct
8 Correct 339 ms 62876 KB Output is correct
9 Correct 153 ms 54160 KB Output is correct
10 Correct 188 ms 54072 KB Output is correct
11 Correct 128 ms 58616 KB Output is correct
12 Correct 134 ms 58716 KB Output is correct
13 Correct 170 ms 62724 KB Output is correct