Submission #1059044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059044		ZeroCool	Synchronization (JOI13_synchronization)	C++14	100 / 100	177 ms	34144 KiB

synchronization

//* 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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40