oj.uz

Submission #531455

# Submission time Handle Problem Language Result Execution time Memory
531455 2022-02-28T18:04:33 Z pnm1384 Inside information (BOI21_servers) C++14
60 / 100
 3500 ms 43572 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[u])
		{
			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]);
	//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 33 ms 22212 KB Output is correct
2 Correct 43 ms 22964 KB Output is correct
3 Correct 40 ms 23036 KB Output is correct
4 Correct 57 ms 23176 KB Output is correct
5 Correct 46 ms 22964 KB Output is correct
6 Correct 54 ms 23048 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 22212 KB Output is correct
2 Correct 43 ms 22964 KB Output is correct
3 Correct 40 ms 23036 KB Output is correct
4 Correct 57 ms 23176 KB Output is correct
5 Correct 46 ms 22964 KB Output is correct
6 Correct 54 ms 23048 KB Output is correct
7 Correct 32 ms 22212 KB Output is correct
8 Correct 51 ms 22508 KB Output is correct
9 Correct 44 ms 22416 KB Output is correct
10 Correct 54 ms 22596 KB Output is correct
11 Correct 49 ms 22444 KB Output is correct
12 Correct 51 ms 22356 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22276 KB Output is correct
2 Execution timed out 3573 ms 35456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22276 KB Output is correct
2 Execution timed out 3573 ms 35456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 22140 KB Output is correct
2 Correct 436 ms 41628 KB Output is correct
3 Correct 430 ms 41496 KB Output is correct
4 Correct 289 ms 43228 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 22140 KB Output is correct
2 Correct 436 ms 41628 KB Output is correct
3 Correct 430 ms 41496 KB Output is correct
4 Correct 289 ms 43228 KB Output is correct
5 Correct 39 ms 22172 KB Output is correct
6 Correct 397 ms 41788 KB Output is correct
7 Correct 377 ms 43332 KB Output is correct
8 Correct 395 ms 41240 KB Output is correct
9 Correct 454 ms 41208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22212 KB Output is correct
2 Correct 283 ms 34688 KB Output is correct
3 Correct 336 ms 32520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22212 KB Output is correct
2 Correct 283 ms 34688 KB Output is correct
3 Correct 336 ms 32520 KB Output is correct
4 Correct 31 ms 22144 KB Output is correct
5 Correct 360 ms 34812 KB Output is correct
6 Correct 303 ms 32740 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22212 KB Output is correct
2 Correct 373 ms 41408 KB Output is correct
3 Correct 393 ms 41444 KB Output is correct
4 Correct 310 ms 43248 KB Output is correct
5 Correct 30 ms 22180 KB Output is correct
6 Correct 288 ms 34692 KB Output is correct
7 Correct 359 ms 32488 KB Output is correct
8 Correct 357 ms 33608 KB Output is correct
9 Correct 319 ms 33856 KB Output is correct
10 Correct 429 ms 38156 KB Output is correct
11 Correct 468 ms 36828 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22212 KB Output is correct
2 Correct 373 ms 41408 KB Output is correct
3 Correct 393 ms 41444 KB Output is correct
4 Correct 310 ms 43248 KB Output is correct
5 Correct 30 ms 22180 KB Output is correct
6 Correct 288 ms 34692 KB Output is correct
7 Correct 359 ms 32488 KB Output is correct
8 Correct 357 ms 33608 KB Output is correct
9 Correct 319 ms 33856 KB Output is correct
10 Correct 429 ms 38156 KB Output is correct
11 Correct 468 ms 36828 KB Output is correct
12 Correct 30 ms 22248 KB Output is correct
13 Correct 438 ms 41836 KB Output is correct
14 Correct 349 ms 43572 KB Output is correct
15 Correct 400 ms 41292 KB Output is correct
16 Correct 432 ms 41132 KB Output is correct
17 Correct 35 ms 22212 KB Output is correct
18 Correct 305 ms 34916 KB Output is correct
19 Correct 392 ms 32736 KB Output is correct
20 Correct 356 ms 34032 KB Output is correct
21 Correct 387 ms 34128 KB Output is correct
22 Correct 577 ms 37148 KB Output is correct
23 Correct 648 ms 37128 KB Output is correct
24 Correct 511 ms 36596 KB Output is correct

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22232 KB Output is correct
2 Correct 55 ms 22976 KB Output is correct
3 Correct 41 ms 23004 KB Output is correct
4 Correct 56 ms 23124 KB Output is correct
5 Correct 43 ms 22920 KB Output is correct
6 Correct 57 ms 23260 KB Output is correct
7 Correct 39 ms 22224 KB Output is correct
8 Execution timed out 3598 ms 35260 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22232 KB Output is correct
2 Correct 55 ms 22976 KB Output is correct
3 Correct 41 ms 23004 KB Output is correct
4 Correct 56 ms 23124 KB Output is correct
5 Correct 43 ms 22920 KB Output is correct
6 Correct 57 ms 23260 KB Output is correct
7 Correct 39 ms 22224 KB Output is correct
8 Execution timed out 3598 ms 35260 KB Time limit exceeded
9 Halted 0 ms 0 KB -