Submission #1246947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246947		ksu2009en	Synchronization (JOI13_synchronization)	C++20	0 / 100	292 ms	32624 KiB

synchronization

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

vector<ll> d[(ll)(1e5 + 7)];
ll time_in[(ll)(1e5 + 7)], time_out[(ll)(1e5 + 7)], t[(ll)(1e5 + 7)][20];

ll step = 0;
void dfs(ll v, ll par){
    time_in[v] = ++step;
    
    t[v][0] = par;
    for(int i = 1; i < 20; i++)
        t[v][i] = t[t[v][i - 1]][i - 1];
    
    for(auto i: d[v])
        if(i != par)
            dfs(i, v);
    
    time_out[v] = ++step;
}

ll f[(ll)(2e5 + 7)];

void add(ll pos, ll val){
    pos++;
    
    for(int i = pos; i < (ll)(2e5 + 7); i += (i & -i))
        f[i] += val;
}

ll get(ll pos){
    pos++;
    
    ll ans = 0;
    for(int i = pos; i > 0; i -= (i & -i))
        ans += f[i];
    
    return ans;
}

ll cur[(ll)(1e5 + 7)], sync[(ll)(1e5 + 7)];
bool lead[(ll)(1e5 + 7)];

ll findlead(ll v){
    if(lead[v])
        return v;
    
    for(int i = 19; i >= 0; i--){
        ll s = get(time_in[t[v][i]]);
        
        if(!s)
            v = t[v][i];
    }
    
    return t[v][0];
}

int main(){
    ll n, m, q;
    cin >> n >> m >> q;
    
    vector<pair<ll, ll>> edge;
    vector<bool> s(n);
    
    for(int i = 0; i < n - 1; i++){
        cur[i + 1] = cur[i + 2] = 1;
        
        ll a, b;
        cin >> a >> b;
        
        d[a].push_back(b);
        d[b].push_back(a);
        
        edge.push_back({a, b});
    }
    
    dfs(1, 1);
    
    for(int i = 1; i <= n; i++){
        add(time_in[i], 1);
        add(time_out[i], -1);
        
        lead[i] = true;
    }
    
    for(int i = 0; i < m; i++){
        ll ind;
        cin >> ind;
        
        ind--;
        
        ll a = edge[ind].first, b = edge[ind].second;
        
        if(time_in[b] < time_in[a])
            swap(a, b);
        
        s[ind] = (!s[ind]);
                
        if(!s[ind]){
            ll l = findlead(a);
            
            cur[b] = sync[b] = cur[l];
            lead[b] = true;
            
            add(time_in[b], 1);
            add(time_out[b], -1);
        }
        else{
            ll l = findlead(a);
            
            ll c = cur[l] + cur[b] - sync[b];
            cur[l] = sync[b] = c;
            
            lead[b] = false;
            
            add(time_in[b], -1);
            add(time_out[b], 1);
        }
    }

    for(int i = 1; i <= q; i++){
        ll x;
        cin >> x;
        
        cout << cur[findlead(x)] << endl;
    }
    
    return 0;
}
/*
 5 6 3
 1 2
 1 3
 2 4
 2 5
 1
 2
 1
 4
 4
 3
 1
 4
 5
 
 */

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40