Submission #644647

#	Time	Username	Problem	Language	Result	Execution time	Memory
644647		khshg	Synchronization (JOI13_synchronization)	C++14	0 / 100	8085 ms	17140 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];

void dfs_sz(int s, int p) {
	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(u, s);
		ssz[s]+=ssz[u];
		if(ssz[adj[s][0]]<ssz[u])
			swap(adj[s][0], u);
	}
}

void build_hld(int s) {
	flat[pos[s]=Tm++]=s;
	trav(u, adj[s]) if(u!=par[s]) {
		anc[u]=(u==adj[s][0]?anc[s]: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 o;
	return query(lv, tl, tm, l, tm);
}

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==-1?0:res);
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	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(0, -1);
	build_hld(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