oj.uz

Submission #531458

# Submission time Handle Problem Language Result Execution time Memory
531458 2022-02-28T18:14:24 Z pnm1384 Inside information (BOI21_servers) C++14
100 / 100
 632 ms 43496 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define F first
#define S second

const int N = 24e4 + 20;
vector<pair<int, int>> adj[N];
int ans[N], Cnt[N], gr[N], fir[N], last[N], fen[N];
vector<pair<int, int>> que1[N];
vector<int> que2[N];
bool hide[N], az[N], be[N];
int Cen;
int bads0[N], bads1[N];
int t0, t1;
pair<int, int> verts[N];
int vert_sz = 0;
int is_que[N];

inline void add(int i, int x)
{
	i++;
	for (; i < N; i += i & -i) fen[i] += x;
	return;
}

inline int get(int i)
{
	i++;
	int ans = 0;
	for (; i > 0; i -= i & -i) ans += fen[i];
	return ans;
}

bool compa(pair<int, int> p1, pair<int, int> p2)
{
	return (make_pair(fir[p1.F], p1.S) < make_pair(fir[p2.F], p2.S));
}

void init(int u, int pp = -1)
{
	Cnt[u] = 1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (v != pp && !hide[v])
		{
			init(v, u);
			Cnt[u] += Cnt[v];
		}
	}
	return;
}

int find_cen(int u, int _n, int pp = -1)
{
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (v != pp && !hide[v] && Cnt[v] * 2 > _n) return find_cen(v, _n, u);
	}
	return u;
}

void dfs1(int u, int pp = -1)
{
	if (az[u])
	{
		bads1[t1++] = u;
		verts[vert_sz++] = {u, 1};
	}
	if (be[u])
	{
		bads0[t0++] = u;
		verts[vert_sz++] = {u, 0};
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (hide[v] || v == pp) continue;
		fir[v] = fir[u]; gr[v] = gr[u]; last[v] = w;
		az[v] = be[v] = false;
		if (w < last[u])
		{
			az[v] = az[u];
		}
		if (w > last[u])
		{
			be[v] = be[u];
		}
		dfs1(v, u);
	}
	return;
}

void dfs2(int u, int pp = -1)
{
	for (pair<int, int> ppp : que1[u])
	{
		int v = ppp.F, qq = ppp.S;
		if (v == Cen)
		{
			if (az[u] && fir[u] < qq) ans[qq] = 1;
			continue;
		}
		if (gr[v] == -1) continue;
		if (az[u] && be[v] && fir[u] < fir[v] && last[v] < qq) ans[qq] = 1;
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v] && v != pp) dfs2(v, u);
	}
	return;
}

void dfs3(int u, int pp = -1)
{
	gr[u] = -1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v] && v != pp) dfs3(v, u);
	}
	return;
}

void decompose(int u)
{
	//cout << "            nwklngkneflweknfl nlkwnflnwl nkn    " << gr[0] << '\n';
	init(u);
	u = find_cen(u, Cnt[u]);
	//assert(u == 0);
	//cout << "        " << u + 1 << '\n';
	vert_sz = t0 = t1 = 0;
	Cen = u;
	int tttt = 1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (!hide[v]) 
		{
			fir[v] = w; last[v] = w; gr[v] = tttt++; az[v] = be[v] = true;
			dfs1(v, u);
		}
	}
	sort(verts, verts + vert_sz, compa);
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) dfs2(v, u);
	}
	for (pair<int, int> ppp : que1[u])
	{
		int v = ppp.F, qq = ppp.S;
		if (gr[v] == -1) continue;
		if (be[v] && last[v] < qq) ans[qq] = 1;
	}
	for (int i = vert_sz - 1; i > -1; i--)
	{
		int x = verts[i].F, ff = verts[i].S;
		if (ff == 0)
		{
			add(last[x], 1);
			continue;
		}
		for (int qq : que2[x])
		{
			ans[qq] += get(qq - 1);
			if (fir[x] < qq) ans[qq]++;
		}
	}
	for (int qq : que2[u])
	{
		ans[qq] += get(qq - 1);
	}
	for (int i = 0; i < t0; i++)
	{
		add(last[bads0[i]], -1);
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) dfs3(v, u);
	}
	hide[u] = true;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) decompose(v);
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(gr, -1, sizeof gr);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n + k - 1; i++)
	{
		char cc;
		cin >> cc;
		if (cc == 'S')
		{
			int u, v;
			cin >> u >> v;
			u--; v--;
			adj[u].push_back({v, i});
			adj[v].push_back({u, i});
			continue;
		}
		if (cc == 'Q')
		{
			is_que[i] = 1;
			int a, d;
			cin >> a >> d;
			a--; d--;
			if (a == d)
			{
				ans[i] = 1;
				continue;
			}
			que1[d].push_back({a, i});
			continue;
		}
		int u;
		cin >> u;
		is_que[i] = 2;
		u--;
		que2[u].push_back(i);
	}
	decompose(0);
	for (int i = 1; i <= n + k - 1; i++)
	{
		if (is_que[i] == 1)
		{
			if (ans[i] != 0) cout << "yes\n";
			else cout << "no\n";
			continue;
		}
		if (is_que[i] == 2) cout << ans[i] + 1 << '\n';
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21300 KB Output is correct
2 Correct 41 ms 21688 KB Output is correct
3 Correct 36 ms 21788 KB Output is correct
4 Correct 42 ms 21800 KB Output is correct
5 Correct 60 ms 21680 KB Output is correct
6 Correct 37 ms 21816 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21300 KB Output is correct
2 Correct 41 ms 21688 KB Output is correct
3 Correct 36 ms 21788 KB Output is correct
4 Correct 42 ms 21800 KB Output is correct
5 Correct 60 ms 21680 KB Output is correct
6 Correct 37 ms 21816 KB Output is correct
7 Correct 29 ms 21432 KB Output is correct
8 Correct 51 ms 21568 KB Output is correct
9 Correct 43 ms 21496 KB Output is correct
10 Correct 49 ms 21704 KB Output is correct
11 Correct 49 ms 21364 KB Output is correct
12 Correct 39 ms 21336 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21324 KB Output is correct
2 Correct 167 ms 32992 KB Output is correct
3 Correct 160 ms 35768 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21324 KB Output is correct
2 Correct 167 ms 32992 KB Output is correct
3 Correct 160 ms 35768 KB Output is correct
4 Correct 33 ms 22208 KB Output is correct
5 Correct 147 ms 35412 KB Output is correct
6 Correct 111 ms 33108 KB Output is correct
7 Correct 109 ms 33288 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21272 KB Output is correct
2 Correct 396 ms 38304 KB Output is correct
3 Correct 344 ms 38252 KB Output is correct
4 Correct 287 ms 39984 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21272 KB Output is correct
2 Correct 396 ms 38304 KB Output is correct
3 Correct 344 ms 38252 KB Output is correct
4 Correct 287 ms 39984 KB Output is correct
5 Correct 31 ms 21444 KB Output is correct
6 Correct 367 ms 38948 KB Output is correct
7 Correct 320 ms 40596 KB Output is correct
8 Correct 393 ms 38660 KB Output is correct
9 Correct 400 ms 38724 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21324 KB Output is correct
2 Correct 274 ms 31496 KB Output is correct
3 Correct 286 ms 29356 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21324 KB Output is correct
2 Correct 274 ms 31496 KB Output is correct
3 Correct 286 ms 29356 KB Output is correct
4 Correct 33 ms 21420 KB Output is correct
5 Correct 321 ms 32184 KB Output is correct
6 Correct 297 ms 30072 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21260 KB Output is correct
2 Correct 380 ms 38324 KB Output is correct
3 Correct 372 ms 38360 KB Output is correct
4 Correct 302 ms 40048 KB Output is correct
5 Correct 29 ms 21444 KB Output is correct
6 Correct 268 ms 31508 KB Output is correct
7 Correct 292 ms 29376 KB Output is correct
8 Correct 332 ms 30380 KB Output is correct
9 Correct 328 ms 30768 KB Output is correct
10 Correct 402 ms 34892 KB Output is correct
11 Correct 429 ms 33816 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21260 KB Output is correct
2 Correct 380 ms 38324 KB Output is correct
3 Correct 372 ms 38360 KB Output is correct
4 Correct 302 ms 40048 KB Output is correct
5 Correct 29 ms 21444 KB Output is correct
6 Correct 268 ms 31508 KB Output is correct
7 Correct 292 ms 29376 KB Output is correct
8 Correct 332 ms 30380 KB Output is correct
9 Correct 328 ms 30768 KB Output is correct
10 Correct 402 ms 34892 KB Output is correct
11 Correct 429 ms 33816 KB Output is correct
12 Correct 31 ms 21408 KB Output is correct
13 Correct 408 ms 38944 KB Output is correct
14 Correct 319 ms 40644 KB Output is correct
15 Correct 405 ms 38736 KB Output is correct
16 Correct 388 ms 38824 KB Output is correct
17 Correct 30 ms 21424 KB Output is correct
18 Correct 293 ms 32004 KB Output is correct
19 Correct 288 ms 29968 KB Output is correct
20 Correct 368 ms 31196 KB Output is correct
21 Correct 362 ms 31432 KB Output is correct
22 Correct 458 ms 34736 KB Output is correct
23 Correct 589 ms 34212 KB Output is correct
24 Correct 560 ms 33448 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21316 KB Output is correct
2 Correct 41 ms 21700 KB Output is correct
3 Correct 38 ms 21768 KB Output is correct
4 Correct 46 ms 21828 KB Output is correct
5 Correct 44 ms 21636 KB Output is correct
6 Correct 43 ms 21724 KB Output is correct
7 Correct 29 ms 21440 KB Output is correct
8 Correct 144 ms 33088 KB Output is correct
9 Correct 157 ms 35760 KB Output is correct
10 Correct 31 ms 22152 KB Output is correct
11 Correct 375 ms 41464 KB Output is correct
12 Correct 399 ms 41456 KB Output is correct
13 Correct 294 ms 43172 KB Output is correct
14 Correct 30 ms 22140 KB Output is correct
15 Correct 274 ms 34728 KB Output is correct
16 Correct 284 ms 32644 KB Output is correct
17 Correct 328 ms 33540 KB Output is correct
18 Correct 346 ms 33860 KB Output is correct
19 Correct 398 ms 38108 KB Output is correct
20 Correct 407 ms 36912 KB Output is correct
21 Correct 175 ms 35580 KB Output is correct
22 Correct 190 ms 35320 KB Output is correct
23 Correct 237 ms 33732 KB Output is correct
24 Correct 244 ms 33896 KB Output is correct
25 Correct 462 ms 38972 KB Output is correct
26 Correct 341 ms 32248 KB Output is correct
27 Correct 294 ms 32132 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21316 KB Output is correct
2 Correct 41 ms 21700 KB Output is correct
3 Correct 38 ms 21768 KB Output is correct
4 Correct 46 ms 21828 KB Output is correct
5 Correct 44 ms 21636 KB Output is correct
6 Correct 43 ms 21724 KB Output is correct
7 Correct 29 ms 21440 KB Output is correct
8 Correct 144 ms 33088 KB Output is correct
9 Correct 157 ms 35760 KB Output is correct
10 Correct 31 ms 22152 KB Output is correct
11 Correct 375 ms 41464 KB Output is correct
12 Correct 399 ms 41456 KB Output is correct
13 Correct 294 ms 43172 KB Output is correct
14 Correct 30 ms 22140 KB Output is correct
15 Correct 274 ms 34728 KB Output is correct
16 Correct 284 ms 32644 KB Output is correct
17 Correct 328 ms 33540 KB Output is correct
18 Correct 346 ms 33860 KB Output is correct
19 Correct 398 ms 38108 KB Output is correct
20 Correct 407 ms 36912 KB Output is correct
21 Correct 175 ms 35580 KB Output is correct
22 Correct 190 ms 35320 KB Output is correct
23 Correct 237 ms 33732 KB Output is correct
24 Correct 244 ms 33896 KB Output is correct
25 Correct 462 ms 38972 KB Output is correct
26 Correct 341 ms 32248 KB Output is correct
27 Correct 294 ms 32132 KB Output is correct
28 Correct 32 ms 22212 KB Output is correct
29 Correct 46 ms 22488 KB Output is correct
30 Correct 41 ms 22344 KB Output is correct
31 Correct 48 ms 22576 KB Output is correct
32 Correct 49 ms 22376 KB Output is correct
33 Correct 40 ms 22284 KB Output is correct
34 Correct 30 ms 22280 KB Output is correct
35 Correct 149 ms 35388 KB Output is correct
36 Correct 106 ms 33160 KB Output is correct
37 Correct 110 ms 33208 KB Output is correct
38 Correct 30 ms 22212 KB Output is correct
39 Correct 370 ms 41768 KB Output is correct
40 Correct 314 ms 43496 KB Output is correct
41 Correct 386 ms 41412 KB Output is correct
42 Correct 391 ms 41176 KB Output is correct
43 Correct 30 ms 22276 KB Output is correct
44 Correct 322 ms 34856 KB Output is correct
45 Correct 294 ms 32740 KB Output is correct
46 Correct 343 ms 34104 KB Output is correct
47 Correct 334 ms 34140 KB Output is correct
48 Correct 470 ms 37044 KB Output is correct
49 Correct 632 ms 37208 KB Output is correct
50 Correct 582 ms 36616 KB Output is correct
51 Correct 131 ms 33716 KB Output is correct
52 Correct 117 ms 34016 KB Output is correct
53 Correct 122 ms 33628 KB Output is correct
54 Correct 121 ms 34376 KB Output is correct
55 Correct 126 ms 33324 KB Output is correct
56 Correct 261 ms 32900 KB Output is correct
57 Correct 358 ms 36792 KB Output is correct
58 Correct 401 ms 32816 KB Output is correct
59 Correct 313 ms 32452 KB Output is correct