oj.uz

Submission #1059044

# Submission time Handle Problem Language Result Execution time Memory
1059044 2024-08-14T16:25:38 Z ZeroCool Synchronization (JOI13_synchronization) C++14
100 / 100
 177 ms 34144 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 1 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 9 ms 10424 KB Output is correct
8 Correct 9 ms 10456 KB Output is correct
9 Correct 9 ms 10200 KB Output is correct
10 Correct 101 ms 30848 KB Output is correct
11 Correct 106 ms 30664 KB Output is correct
12 Correct 147 ms 33372 KB Output is correct
13 Correct 56 ms 30652 KB Output is correct
14 Correct 63 ms 30148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 30916 KB Output is correct
2 Correct 59 ms 30664 KB Output is correct
3 Correct 59 ms 32708 KB Output is correct
4 Correct 60 ms 32708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 12 ms 10632 KB Output is correct
8 Correct 177 ms 34016 KB Output is correct
9 Correct 172 ms 34144 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 33988 KB Output is correct
2 Correct 99 ms 33580 KB Output is correct
3 Correct 93 ms 33988 KB Output is correct
4 Correct 91 ms 33936 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7420 KB Output is correct
5 Correct 2 ms 7520 KB Output is correct
6 Correct 11 ms 10492 KB Output is correct
7 Correct 130 ms 31512 KB Output is correct
8 Correct 174 ms 34072 KB Output is correct
9 Correct 77 ms 31676 KB Output is correct
10 Correct 91 ms 31428 KB Output is correct
11 Correct 80 ms 32196 KB Output is correct
12 Correct 81 ms 32264 KB Output is correct
13 Correct 93 ms 33964 KB Output is correct