Submission #644712

#	Time	Username	Problem	Language	Result	Execution time	Memory
644712		khshg	Synchronization (JOI13_synchronization)	C++14	0 / 100	191 ms	16748 KiB

synchronization

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

/*	
			    `         '
;,,,             `       '             ,,,;
`Y3S3333bo.       :     :       .od3333Y3S'
  3331O3D033b.     :   :     .d333313D033
  3L0V3Y'  `Y3b.   `   '   .d3Y'  `YL0V33
 jTH33!  .db.  Yb. '   ' .dY  .db.  3TH33!
   `333  Y33Y    `b ( ) d'    Y33Y  333'
    3MYb  '"        ,',        "'  dMY3
   j3pr3C10USgf"'   ':'   `"?g3pr3C10USk
     'Y'   .3'     d' 'b     '3.   'Y'
      !   .3' db  d'1 1`b  db '3.   !
         d33  `'  3 ; ; 3  `'  33b
        d331b   .g8 ',' 8g.   d133b
       :333LOV333Y'     'Y33L0V3333:
       '! TH33333'       `333TH33 !'
          '3Y  `Y         Y'  Y3'
           Y                   Y
		   !                   !
*/

using ll = long long;
using db = long double;
using str = string;

// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mt make_tuple
#define mp make_pair
#define ff first
#define ss second

// vector
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
using vd = V<db>;
using vb = V<bool>;
using vpi = V<pi>;
using vpl = V<pl>;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)((a).size())
#define ini(a, b) memset(a, b, sizeof(a))
#define rsz resize
#define pb push_back
#define eb emplace_back
#define ins insert
#define arr array

#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return (int)(lb(all(a), b)-a.begin()); }
template<class T> int upb(V<T>& a, const T& b) { return (int)(ub(all(a), b)-a.begin()); }

// loops
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ceil()
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down floor()

// consts
const int MOD = (int)1e9+7; // 998244353;
const int INF = (int)0x3f3f3f3f; // INF+INF < INF_MAX
const ll INFL = ll(0x3f3f3f3f3f3f3f3f); // INFL+INFL < LLONG_MAX
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};

// statement
const int maxn=100000;
int N, M, Q, info[maxn], Cinfo[maxn];
bool A[maxn];
pi edge[maxn];
vi adj[maxn];

//hld
int par[4*maxn], ssz[maxn];
int Tm, pos[maxn], anc[maxn], flat[maxn], heavy[maxn];

void dfs_sz(int p, int s) {
	par[s]=p;
	ssz[s]=info[s]=1;/*
	if(sz(adj[s])>=2&&adj[s][0]==p)
		swap(adj[s][0], adj[s][1]);*/
	trav(u, adj[s]) if(u!=p) {
		dfs_sz(s, u);
		ssz[s]+=ssz[u];/*
		if(ssz[adj[s][0]]<ssz[u])
			swap(adj[s][0], u);*/
		if(heavy[s]==-1||ssz[heavy[s]]<ssz[u])
			heavy[s]=u;
	}
}
/*
int init(int p, int u) {
	ssz[u] = 1;
	info[u] = 1;
	par[u] = p;
	for (int v : adj[u]) {
		if (v == p) continue;
		ssz[u] += init(u, v);
		if (heavy[u] == -1 || ssz[v] > ssz[heavy[u]]) {
			heavy[u] = v;
		}
	}
	return ssz[u];
}*/
 
void build_hld(int p, int u, int r) {
	anc[u] = r;
	pos[u] = Tm;
	flat[Tm] = u;
	++Tm;
	if(Tm<0)
		exit(1);
	if (heavy[u] == -1)
		return;
	build_hld(u, heavy[u], r);
	for (int v : adj[u]) {
		if (v == p || v == heavy[u]) continue;
		build_hld(u, v, v);
	}
}


/*
void build_hld(int s) {
	pos[s]=Tm;
	flat[Tm]=s;
	++Tm;
	trav(u, adj[s]) if(u!=par[s]) {
		if(u==adj[s][0])
			anc[u]=anc[s];
		else
			anc[u]=u;
		build_hld(u);
	}
}*/

//segment tree
int st[maxn];
bool __[maxn];

#define tm ((tl+tr)/2)
#define lv (2*v+1)
#define rv (2*v+2)

void build_st(int v, int tl, int tr) {
	if(tl==tr)
		st[v]=flat[tl];
	else {
		build_st(lv, tl, tm);
		build_st(rv, tm+1, tr);
		st[v]=st[rv];
	}
}

void update(int v, int tl, int tr, int ind) {
	if(tl==tr) {
		__[tl]^=1;
		st[v]=(__[tl]?-1:flat[tl]);
	} else {
		if(ind<=tm)
			update(lv, tl, tm, ind);
		else
			update(rv, tm+1, tr, ind);
		st[v]=st[(st[rv]==-1?lv:rv)];
	}
}

int query(int v, int tl, int tr, int l, int r) {
	if(tl==l&&tr==r)
		return st[v];
	if(r<=tm)
		return query(lv, tl, tm, l, r);
	if(l>tm)
		return query(rv, tm+1, tr, l, r);
	int o=query(rv, tm+1, tr, tm+1, r);
	if(o==-1)
		return query(lv, tl, tm, l, tm);
	return o;
}

int q(int s) {
	int res=-1;
	while(res==-1&&s!=-1) {
		res=query(0, 0, N-1, pos[anc[s]], pos[s]);
		s=par[anc[s]];
	}
	return res;
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	ini(heavy, -1);
	cin >> N >> M >> Q;
	F0R(i, N-1) {
		int U, V; cin >> U >> V;
		--U; --V;
		edge[i]=mp(U, V);
		adj[U].pb(V);
		adj[V].pb(U);
	}
	dfs_sz(-1, 0);
	build_hld(-1, 0, 0);
	build_st(0, 0, N-1);
	F0R(i, M) {
		int D, U, V; cin >> D;
		--D;
		tie(U, V)=edge[D];
		if(par[U]==V)
			swap(U, V);
		if(!A[D])
			info[q(U)]+=info[V]-Cinfo[V];
		else
			info[V]=Cinfo[V]=info[q(U)];
		update(0, 0, N-1, pos[V]);
		A[D]^=1;
	}
	F0R(i, Q) {
		int C; cin >> C;
		--C;
		cout << info[q(C)] << '\n';
	}
	return 11^3^1<<3;
}

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