제출 #1311546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311546		reginox	동기화 (JOI13_synchronization)	C++20	100 / 100	410 ms	27316 KiB

synchronization

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;

struct Fenwick{
	int n; vector<vector<ll>> t;
    void resize(int _n){
		n = _n;
        t.assign(n+1, vector<ll>(2, 0));
    }
	void upd(int tp, int id, ll x){
		for(int i = id; i <= n; i+=i&(-i)) t[i][tp]+=x;
	}
	void add(int l, int r, ll x){
		upd(0, l, x); upd(0, r+1, -x);
		upd(1, l, x*(l-1)); upd(1, r+1, -x*r);	
	}
	ll sum(int tp, int id){
		ll res = 0;
		for(int i = id; i > 0; i-=i&(-i)) res+=t[i][tp];
		return res;
	}
	ll get(int x){
		return sum(0, x)*(ll)x  - sum(1, x);
	}
	ll query(int a, int b){
		return get(b) - get(a-1);
	}
};

const int N = 3e5+3;
int n, m, q;
vector<int> g[N];
pi eg[N];
int a[N], c[N];
int tin[N], tout[N], timer, depth[N];
int sp[N][17];
Fenwick f;

int findroot(int x){
  int v = f.query(tin[x], tin[x]);
  for(int i = 16; i >= 0; i--){
    if(f.query(tin[sp[x][i]], tin[sp[x][i]]) == v){
      x = sp[x][i];
    }
  }
  if(x == 0) return 1;
  return x;
}

void dfs(int u, int p){
  for(int i = 1; i <= 16; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
  depth[u] = depth[p] + 1;
  tin[u] = ++timer;
  for(auto v:g[u]){
    if(v == p) continue;
    sp[v][0] = u;
    dfs(v, u);
  }
  tout[u] = timer;
}

void join(int e){
  int u = eg[e].first, v = eg[e].second;
  if(depth[u] > depth[v]) swap(u, v);
  f.add(tin[v], tout[v], -1);
  u = findroot(u);
  a[u] += a[v] - c[v];
}

void cut(int e){
  int u = eg[e].first, v = eg[e].second;
  if(depth[u] > depth[v]) swap(u, v);
  u = findroot(u);
  c[v] = a[v] = a[u];
  f.add(tin[v], tout[v], 1);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m >> q;
  f.resize(n);
  for(int i = 1; i < n; i++){
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    eg[i] = {u, v};
  }
  fill_n(a+1, n, 1);
  dfs(1, 0);
  for(int i = 1; i <= n; i++) 
    f.add(tin[i], tin[i], depth[i] - 1);
  vector<bool> status(n, false);
  while(m--){
    int x; cin >> x;
    if(status[x] == false) join(x);
    else cut(x);
    status[x] = !status[x];
    // cout << x << "\n";
    // for(int i = 1; i <= n; i++) cout << a[i] << " ";
    // cout << "\n";
    // for(int i = 1; i <= n; i++) cout << f.query(i, i) << " ";
    // cout << "\n";
    // for(int i = 1; i <= n; i++) cout << findroot(i) << " ";
    // cout << "\n\n";
  }
  while(q--){
    int x; cin >> x;
    // cout << findroot(x) << "\n";
    cout << a[findroot(x)] << "\n";
  }
  return 0;
}

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