oj.uz

Submission #527919

# Submission time Handle Problem Language Result Execution time Memory
527919 2022-02-18T17:31:32 Z pooyashams Inside information (BOI21_servers) C++14
100 / 100
 604 ms 51360 KB 
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 3e5+10;
const int lgmx = 20;

struct fwt
{
	vector<int> fen;
	int n;
	fwt(){};
	fwt(int _n)
	{
		n = _n+10;
		fen = vector<int>(n, 0);
	}
	inline void add(int r, int x)
	{
		for(r+=3; r < n; r += r&-r)
			fen[r] += x;
	}
	inline int get(int r)
	{
		int out = 0;
		for(r+=3; r > 0; r -= r&-r)
			out += fen[r];
		return out;
	}
	inline int get(int l, int r)
	{
		return get(r-1)-get(l-1);
	}
} fen;

vector<pii> G[maxn];
int type[maxn];
int as[maxn];
int bs[maxn];
int ans[maxn];
vector<int> qrs[maxn];

#define u e.first
#define w e.second

int hight[maxn];
int par[maxn][lgmx];
int wpar[maxn];
int fmfi[maxn];
int fmfd[maxn];

void dfslca(int v, int p, int h, int x)
{
	hight[v] = h;
	wpar[v] = x;
	par[v][0] = p;
	for(int k = 1; k < lgmx; k++)
		par[v][k] = par[par[v][k-1]][k-1];
	for(pii e: G[v])
	{
		if(u == p) continue;
		if(x < w)
		{
			fmfd[u] = fmfd[v];
			fmfi[u] = h-1;
		}
		else // x > w (w != x)
		{
			fmfd[u] = h-1;
			fmfi[u] = fmfi[v];
		}
		dfslca(u, v, h+1, w);
	}
}

inline int getpar(int v, int k)
{
	for( ; k > 0; k -= k&-k)
		v = par[v][__builtin_ctz(k)];
	return v;
}

inline pii lca(int x, int y)
{
	if(hight[x] > hight[y])
		x = getpar(x, hight[x]-hight[y]);
	else
		y = getpar(y, hight[y]-hight[x]);
	if(x == y) return {x, y};
	for(int i = lgmx-1; i >= 0; i--)
	{
		if(par[x][i] != par[y][i])
		{
			x = par[x][i];
			y = par[y][i];
		}
	}
	return {x, y};
}

bool dead[maxn];
int sz[maxn];

int pre(int v, int p)
{
	sz[v] = 1;
	for(pii e: G[v])
		if(!dead[u] and u != p)
			sz[v] += pre(u, v);
	return sz[v];
}

int find_cntrd(int v, int p, int s)
{
	for(pii e: G[v])
		if(!dead[u] and u != p and sz[u]*2 > s)
			return find_cntrd(u, v, s);
	return v;
}

void addans(int v, int p, int x)
{
	for(int i: qrs[v])
		ans[i] += fen.get(i);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w > x))
			addans(u, v, w);
}
void addvrt(int v, int p, int x)
{
	fen.add(x, 1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			addvrt(u, v, w);
}
void clrvrt(int v, int p, int x)
{
	fen.add(x, -1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			clrvrt(u, v, w);
}
void srcadd(int v, int p, int x)
{
	fen.add(x, 1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			srcadd(u, v, w);
}
void srcclr(int v, int p, int x)
{
	fen.add(x, -1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			srcclr(u, v, w);
}
void srcapp(int v, int p, int x, int ix)
{
	for(int i: qrs[v])
		if(i > ix)
			ans[i]++;
	for(pii e: G[v])
		if(not (u == p or dead[u] or w > x))
			srcapp(u, v, w, ix);
}

void dcmps(int v)
{
	v = find_cntrd(v, v, pre(v, v));
	//cerr << "--- " << v << " ---" << endl;
	dead[v] = true;
	for(pii e: G[v])
	{
		if(dead[u]) continue;
		addans(u, v, w);
		addvrt(u, v, w);
	}
	for(pii e: G[v])
		if(!dead[u])
			clrvrt(u, v, w);
	for(pii e: G[v])
		if(!dead[u])
			srcadd(u, v, w);
	for(int i: qrs[v])
		ans[i] += fen.get(i);
	for(pii e: G[v])
		if(!dead[u])
			srcclr(u, v, w);
	for(pii e: G[v])
		if(!dead[u])
			srcapp(u, v, w, w);
	for(pii e: G[v])
		if(!dead[u])
			dcmps(u);
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,k; cin >> n >> k;
	int q = n+k-1;
	fen = fwt(q);
	for(int i = 0; i < q; i++)
	{
		char c; cin >> c;
		if(c == 'S')
		{
			type[i] = 0;
			cin >> as[i] >> bs[i];
			as[i]--; bs[i]--;
			G[as[i]].push_back({bs[i], i});
			G[bs[i]].push_back({as[i], i});
		}
		else if(c == 'Q')
		{
			type[i] = 1;
			cin >> as[i] >> bs[i];
			as[i]--; bs[i]--;
		}
		else // c == 'C'
		{
			type[i] = 2;
			cin >> as[i];
			as[i]--;
			qrs[as[i]].push_back(i);
		}
	}
	for(int v = 0; v < n; v++)
		sort(G[v].begin(), G[v].end(), [&](pii i, pii j){ return i.second > j.second; });
	fmfi[0] = -1;
	fmfd[0] = -1;
	dfslca(0, 0, 0, 0);
	//for(int i = 0; i < n; i++) cerr << wpar[i] << " "; cerr << endl;
	for(int i = 0; i < q; i++)
	{
		if(type[i] == 1)
		{
			int a = as[i];
			int b = bs[i];
			if(a == b)
			{
				ans[i] = 1;
				continue;
			}
			pii p = lca(a, b);
			int ap = p.first;
			int bp = p.second;
			if(ap == bp)
			{
				if(ap == a)
				{
					int r = getpar(b, hight[b]-hight[a]-1);
					ans[i] = (hight[a] > fmfi[b] and wpar[r] < i);
				}
				else // ap == b
					ans[i] = (hight[b] > fmfd[a] and wpar[a] < i);
			}
			else
			{
				int r = par[ap][0];
				ans[i] = (wpar[a] < i and wpar[ap] > wpar[bp] and hight[r] > max(fmfi[b], fmfd[a]) );
			}
		}
	}
	dcmps(0);
	for(int i = 0; i < q; i++)
	{
		if(type[i] == 1)
		{
			if(ans[i]) cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else if(type[i] == 2)
		{
			cout << ans[i]+1 << endl;
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 169 ms 18004 KB Output is correct
2 Correct 174 ms 19200 KB Output is correct
3 Correct 171 ms 19180 KB Output is correct
4 Correct 203 ms 19268 KB Output is correct
5 Correct 167 ms 19452 KB Output is correct
6 Correct 173 ms 19264 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 169 ms 18004 KB Output is correct
2 Correct 174 ms 19200 KB Output is correct
3 Correct 171 ms 19180 KB Output is correct
4 Correct 203 ms 19268 KB Output is correct
5 Correct 167 ms 19452 KB Output is correct
6 Correct 173 ms 19264 KB Output is correct
7 Correct 183 ms 18040 KB Output is correct
8 Correct 181 ms 19276 KB Output is correct
9 Correct 181 ms 19292 KB Output is correct
10 Correct 173 ms 19412 KB Output is correct
11 Correct 166 ms 19616 KB Output is correct
12 Correct 176 ms 19268 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 18072 KB Output is correct
2 Correct 262 ms 38884 KB Output is correct
3 Correct 267 ms 38932 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 18072 KB Output is correct
2 Correct 262 ms 38884 KB Output is correct
3 Correct 267 ms 38932 KB Output is correct
4 Correct 170 ms 18276 KB Output is correct
5 Correct 279 ms 38908 KB Output is correct
6 Correct 234 ms 38604 KB Output is correct
7 Correct 237 ms 38804 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18076 KB Output is correct
2 Correct 331 ms 49696 KB Output is correct
3 Correct 363 ms 49772 KB Output is correct
4 Correct 377 ms 49708 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18076 KB Output is correct
2 Correct 331 ms 49696 KB Output is correct
3 Correct 363 ms 49772 KB Output is correct
4 Correct 377 ms 49708 KB Output is correct
5 Correct 167 ms 18024 KB Output is correct
6 Correct 376 ms 50708 KB Output is correct
7 Correct 418 ms 50944 KB Output is correct
8 Correct 454 ms 51144 KB Output is correct
9 Correct 395 ms 51232 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 18032 KB Output is correct
2 Correct 368 ms 39400 KB Output is correct
3 Correct 318 ms 39604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 18032 KB Output is correct
2 Correct 368 ms 39400 KB Output is correct
3 Correct 318 ms 39604 KB Output is correct
4 Correct 188 ms 18020 KB Output is correct
5 Correct 395 ms 40500 KB Output is correct
6 Correct 345 ms 40308 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 17988 KB Output is correct
2 Correct 361 ms 49780 KB Output is correct
3 Correct 323 ms 49744 KB Output is correct
4 Correct 450 ms 49716 KB Output is correct
5 Correct 162 ms 18068 KB Output is correct
6 Correct 366 ms 39364 KB Output is correct
7 Correct 306 ms 39728 KB Output is correct
8 Correct 468 ms 40256 KB Output is correct
9 Correct 379 ms 40236 KB Output is correct
10 Correct 443 ms 45516 KB Output is correct
11 Correct 508 ms 44796 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 17988 KB Output is correct
2 Correct 361 ms 49780 KB Output is correct
3 Correct 323 ms 49744 KB Output is correct
4 Correct 450 ms 49716 KB Output is correct
5 Correct 162 ms 18068 KB Output is correct
6 Correct 366 ms 39364 KB Output is correct
7 Correct 306 ms 39728 KB Output is correct
8 Correct 468 ms 40256 KB Output is correct
9 Correct 379 ms 40236 KB Output is correct
10 Correct 443 ms 45516 KB Output is correct
11 Correct 508 ms 44796 KB Output is correct
12 Correct 164 ms 18120 KB Output is correct
13 Correct 423 ms 50908 KB Output is correct
14 Correct 469 ms 50880 KB Output is correct
15 Correct 401 ms 51196 KB Output is correct
16 Correct 417 ms 51140 KB Output is correct
17 Correct 170 ms 18064 KB Output is correct
18 Correct 388 ms 40516 KB Output is correct
19 Correct 345 ms 40344 KB Output is correct
20 Correct 373 ms 41224 KB Output is correct
21 Correct 386 ms 41348 KB Output is correct
22 Correct 576 ms 44872 KB Output is correct
23 Correct 585 ms 44972 KB Output is correct
24 Correct 591 ms 43880 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 178 ms 17988 KB Output is correct
2 Correct 195 ms 19148 KB Output is correct
3 Correct 173 ms 19472 KB Output is correct
4 Correct 184 ms 19264 KB Output is correct
5 Correct 165 ms 19536 KB Output is correct
6 Correct 185 ms 19256 KB Output is correct
7 Correct 161 ms 18096 KB Output is correct
8 Correct 265 ms 39072 KB Output is correct
9 Correct 296 ms 38968 KB Output is correct
10 Correct 153 ms 18088 KB Output is correct
11 Correct 355 ms 49736 KB Output is correct
12 Correct 442 ms 49812 KB Output is correct
13 Correct 394 ms 49676 KB Output is correct
14 Correct 166 ms 18080 KB Output is correct
15 Correct 367 ms 39272 KB Output is correct
16 Correct 361 ms 39656 KB Output is correct
17 Correct 347 ms 40200 KB Output is correct
18 Correct 367 ms 40296 KB Output is correct
19 Correct 520 ms 45464 KB Output is correct
20 Correct 473 ms 44596 KB Output is correct
21 Correct 320 ms 39536 KB Output is correct
22 Correct 312 ms 39544 KB Output is correct
23 Correct 320 ms 39872 KB Output is correct
24 Correct 347 ms 39852 KB Output is correct
25 Correct 418 ms 42728 KB Output is correct
26 Correct 375 ms 38884 KB Output is correct
27 Correct 361 ms 38916 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 178 ms 17988 KB Output is correct
2 Correct 195 ms 19148 KB Output is correct
3 Correct 173 ms 19472 KB Output is correct
4 Correct 184 ms 19264 KB Output is correct
5 Correct 165 ms 19536 KB Output is correct
6 Correct 185 ms 19256 KB Output is correct
7 Correct 161 ms 18096 KB Output is correct
8 Correct 265 ms 39072 KB Output is correct
9 Correct 296 ms 38968 KB Output is correct
10 Correct 153 ms 18088 KB Output is correct
11 Correct 355 ms 49736 KB Output is correct
12 Correct 442 ms 49812 KB Output is correct
13 Correct 394 ms 49676 KB Output is correct
14 Correct 166 ms 18080 KB Output is correct
15 Correct 367 ms 39272 KB Output is correct
16 Correct 361 ms 39656 KB Output is correct
17 Correct 347 ms 40200 KB Output is correct
18 Correct 367 ms 40296 KB Output is correct
19 Correct 520 ms 45464 KB Output is correct
20 Correct 473 ms 44596 KB Output is correct
21 Correct 320 ms 39536 KB Output is correct
22 Correct 312 ms 39544 KB Output is correct
23 Correct 320 ms 39872 KB Output is correct
24 Correct 347 ms 39852 KB Output is correct
25 Correct 418 ms 42728 KB Output is correct
26 Correct 375 ms 38884 KB Output is correct
27 Correct 361 ms 38916 KB Output is correct
28 Correct 185 ms 18192 KB Output is correct
29 Correct 178 ms 19324 KB Output is correct
30 Correct 166 ms 19268 KB Output is correct
31 Correct 177 ms 19400 KB Output is correct
32 Correct 204 ms 19716 KB Output is correct
33 Correct 167 ms 19364 KB Output is correct
34 Correct 198 ms 18132 KB Output is correct
35 Correct 264 ms 38900 KB Output is correct
36 Correct 233 ms 38536 KB Output is correct
37 Correct 282 ms 38600 KB Output is correct
38 Correct 153 ms 18112 KB Output is correct
39 Correct 400 ms 50752 KB Output is correct
40 Correct 396 ms 50884 KB Output is correct
41 Correct 381 ms 51360 KB Output is correct
42 Correct 435 ms 51140 KB Output is correct
43 Correct 193 ms 18092 KB Output is correct
44 Correct 400 ms 40496 KB Output is correct
45 Correct 353 ms 40392 KB Output is correct
46 Correct 422 ms 41156 KB Output is correct
47 Correct 386 ms 41264 KB Output is correct
48 Correct 582 ms 44864 KB Output is correct
49 Correct 604 ms 44932 KB Output is correct
50 Correct 525 ms 44044 KB Output is correct
51 Correct 256 ms 39728 KB Output is correct
52 Correct 260 ms 39504 KB Output is correct
53 Correct 241 ms 39080 KB Output is correct
54 Correct 291 ms 39692 KB Output is correct
55 Correct 260 ms 39452 KB Output is correct
56 Correct 321 ms 39844 KB Output is correct
57 Correct 403 ms 42688 KB Output is correct
58 Correct 460 ms 40308 KB Output is correct
59 Correct 396 ms 39316 KB Output is correct