oj.uz

Submission #957915

# Submission time Handle Problem Language Result Execution time Memory
957915 2024-04-04T13:32:45 Z vjudge1 Synchronization (JOI13_synchronization) C++17
100 / 100
 305 ms 34408 KB 
//* Nigga we hit em up like mutherfucking Tupac Shakur

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
      
using namespace std;
using namespace __gnu_pbds;
      
template <typename T>
using oset = tree<T,null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update>;
      
#define int long long
          
#define pb push_back
#define ins insert
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
  
          
using ll = long long;
using ld = long double;

#define endl '\n'

#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
        
#define da cout<<"DA"<<endl
#define ne cout<<"NE"<<endl
          
#define send ios::sync_with_stdio(false);
#define help cin.tie(0);
          
void solve(int T);
          
const int N = 1e5  + 10;
const int M = 5e5 + 10;
const int SQRT = sqrt(N);
const int LOG = 20;
const int INF = 1e18;
const int MOD = 123456789;
const ld EPS = 1e-9;

  
int ans;
int n, m,k, q, l, r, x, y, z, mx, mn;
  
  
          
int32_t main(){
    auto begin = chrono::high_resolution_clock::now();
    cout<<setprecision(7)<<fixed;
              
    send help;
          
    int tt = 1;
    //cin>>tt; //? Comment if no testcases
    for(int i = 1;i<=tt;i++){
        cerr<<"Case "<<i<<": "<<endl;
        solve(i);
    }
    auto end = chrono::high_resolution_clock::now();
    cerr<<"Time: "<<chrono::duration_cast<chrono::duration<double>>(end - begin).count()<<endl;
    return 0;
}



struct FWT{
    vector<int> bit;
    int n;
    FWT(int _n){
        n = _n;
        bit.resize(n + 69);
    }

    inline int lsb(int x){
        return x & -x;
    }

    void modify(int i,int v){
        for(i++;i<bit.size();i += lsb(i))bit[i] += v;
    }

    int query(int i){
        int res = 0;
        for(i++;i;i-=lsb(i))res += bit[i];
        return res;
    }
};

int up[N][LOG];
int dep[N];
vector<int> g[N];

int T=0;

int tin[N];
int tout[N];

void dfs(int x,int p){
    up[x][0] = p;
    tin[x] = ++T;
    for(int i = 1;i<LOG;i++)up[x][i] = up[up[x][i-1]][i-1];

    for(auto u : g[x]){
        if(u == p)continue;
        dep[u] = dep[x] + 1;
        dfs(u, x);
    }
    tout[x] = T;
}

FWT fwt(N);

int find(int x){
    int y = x;
    for(int i = LOG-1;i>=0;i--){
        if(fwt.query(tin[x]) == fwt.query(tin[up[y][i]]))y = up[y][i];
    }
    return y;
}

bool A[N];


void solve(int T){
    cin>>n>>m>>q;
    vector<pair<int,int> > e;
    for(int i = 1;i<n;i++){
        int u, v;
        cin>>u>>v;
        --u, --v;
        g[u].pb(v);
        g[v].pb(u);

        e.pb({u, v});
    }

    dfs(0, 0);
    int ans[n];
    int last[n];
    for(int i = 0;i<n;i++){
        ans[i] = 1;
        last[i] = 0;
        fwt.modify(tin[i], 1);
        fwt.modify(tout[i]+1, -1);

    }

    for(int i = 0;i<m;i++){
        int x;
        cin>>x;
        --x;
        int u = e[x].first;
        int v = e[x].second;

        if(dep[u] > dep[v])swap(u, v);
        int r = find(u);
        if(A[x]){
            ans[v] = last[v] = ans[r];
            fwt.modify(tin[v], 1);
            fwt.modify(tout[v] + 1, -1);
        }else{
            ans[r] += ans[v] - last[v];
            fwt.modify(tin[v], -1);
            fwt.modify(tout[v] + 1, 1);
        }

        A[x] = !A[x];
    }

    for(int i = 0;i<q;i++){
        int x;
        cin>>x;
        --x;
        cout<<ans[find(x)]<<endl;
    }
}   
  
  
  
//! Te molam da raboti !!

Compilation message

synchronization.cpp: In member function 'void FWT::modify(long long int, long long int)':
synchronization.cpp:86:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(i++;i<bit.size();i += lsb(i))bit[i] += v;
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 3 ms 7440 KB Output is correct
7 Correct 15 ms 10200 KB Output is correct
8 Correct 14 ms 10200 KB Output is correct
9 Correct 15 ms 10196 KB Output is correct
10 Correct 211 ms 30844 KB Output is correct
11 Correct 208 ms 30848 KB Output is correct
12 Correct 226 ms 33212 KB Output is correct
13 Correct 104 ms 30512 KB Output is correct
14 Correct 184 ms 30092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 31008 KB Output is correct
2 Correct 89 ms 30716 KB Output is correct
3 Correct 103 ms 32564 KB Output is correct
4 Correct 124 ms 32756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7420 KB Output is correct
3 Correct 2 ms 7416 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 23 ms 10744 KB Output is correct
8 Correct 270 ms 34144 KB Output is correct
9 Correct 279 ms 34408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 34016 KB Output is correct
2 Correct 149 ms 33760 KB Output is correct
3 Correct 162 ms 33768 KB Output is correct
4 Correct 147 ms 33980 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 16 ms 10452 KB Output is correct
7 Correct 234 ms 31616 KB Output is correct
8 Correct 249 ms 34140 KB Output is correct
9 Correct 105 ms 31672 KB Output is correct
10 Correct 151 ms 31688 KB Output is correct
11 Correct 113 ms 32316 KB Output is correct
12 Correct 124 ms 32192 KB Output is correct
13 Correct 135 ms 33976 KB Output is correct