oj.uz

Submission #644725

# Submission time Handle Problem Language Result Execution time Memory
644725 2022-09-25T06:47:00 Z khshg Synchronization (JOI13_synchronization) C++14
100 / 100
 183 ms 28556 KB 
#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=400000;
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) {
	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[4*maxn];
bool __[4*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) {
		if(pos[anc[s]]>pos[s])
			exit(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 8 ms 9812 KB Output is correct
7 Correct 15 ms 10580 KB Output is correct
8 Correct 15 ms 10580 KB Output is correct
9 Correct 14 ms 10580 KB Output is correct
10 Correct 155 ms 17748 KB Output is correct
11 Correct 151 ms 17672 KB Output is correct
12 Correct 116 ms 27772 KB Output is correct
13 Correct 93 ms 19956 KB Output is correct
14 Correct 104 ms 19088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21640 KB Output is correct
2 Correct 84 ms 23340 KB Output is correct
3 Correct 83 ms 26804 KB Output is correct
4 Correct 65 ms 26772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 19 ms 11384 KB Output is correct
8 Correct 183 ms 25676 KB Output is correct
9 Correct 148 ms 28520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 25592 KB Output is correct
2 Correct 88 ms 27852 KB Output is correct
3 Correct 88 ms 27992 KB Output is correct
4 Correct 85 ms 27976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 17 ms 10580 KB Output is correct
7 Correct 180 ms 17992 KB Output is correct
8 Correct 157 ms 28556 KB Output is correct
9 Correct 119 ms 21088 KB Output is correct
10 Correct 173 ms 20276 KB Output is correct
11 Correct 115 ms 24584 KB Output is correct
12 Correct 114 ms 24588 KB Output is correct
13 Correct 86 ms 28056 KB Output is correct