oj.uz

Submission #631544

# Submission time Handle Problem Language Result Execution time Memory
631544 2022-08-18T08:21:00 Z LittleCube Jail (JOI22_jail) C++14
77 / 100
 5000 ms 756216 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int T, N, M, pre[1200005], dis[1200005], s[1200005], e[1200005], deg[8000005], fr[1200005], to[1200005], Hhead[1200005], Hsz[1200005], Hpos[1200005], idx, ts;
pii io[1200005];
vector<int> E[1200005], topo[8000005];

struct HLD
{
	// 0: start, 1: end
	int root[1600005][2] = {};
	int l[8000005] = {};
	int r[8000005] = {};
	
	void init()
	{
		for(int i = 1; i <= 6 * N; i++)
			l[i] = r[i] = 0;
		for(int i = 1; i <= N; i++)
			root[i][0] = root[i][1] = 0;
		for(int i = 1; i <= N; i++)
			if(Hsz[i])
			{
				// cout << "HLD: " << i << '\n';
				root[i][0] = ++idx;
				segInit(idx, 1, Hsz[i], 0);
				root[i][1] = ++idx;
				segInit(idx, 1, Hsz[i], 1);
			}
	}

	void segInit(int i, int L, int R, int type)
	{
		// cout << i << ' ' << L << ' ' << R << ' ' << type << '\n';
		if(L == R)
			return;
		int mid = (L + R) / 2;
		l[i] = ++idx;
		segInit(l[i], L, mid, type);
		r[i] = ++idx;
		segInit(r[i], mid + 1, R, type);

		if(type == 0)
		{
			topo[l[i]].emplace_back(i);
			topo[r[i]].emplace_back(i);
		}
		else
		{
			topo[i].emplace_back(l[i]);
			topo[i].emplace_back(r[i]);
		}
	}

	void segInsert(int i, int L, int R, int pos, int j, int type)
	{
		if(L == R)
		{
			// cout << i << ' ' << j << ' ' << type << '\n';
			if(type == 0)
				topo[j].emplace_back(i);
			else 
				topo[i].emplace_back(j);
		}
		else
		{
			int mid = (L + R) / 2;
			if(pos <= mid)
				segInsert(l[i], L, mid, pos, j, type);
			else
				segInsert(r[i], mid + 1, R, pos, j, type);
		}
	}

	void segEdge(int r1, int r2, int L, int R, int j, int mL, int mR)
	{
		if(mL <= L && R <= mR)
		{
			topo[r1].emplace_back(j);
			topo[j].emplace_back(r2);
		}
		else if(R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			segEdge(l[r1], l[r2], L, mid, j, mL, mR);
			segEdge(r[r1], r[r2], mid + 1, R, j, mL, mR);
		}
	}
}hld;

void dfs(int u)
{
	io[u].F = ++ts;
	for(int v : E[u])
		if(pre[u] != v)
		{
			pre[v] = u;
			dis[v] = dis[u] + 1;
			dfs(v);
		}
	io[u].S = ts;
}

void decompose(int u, int h)
{
	int deep = 0;
	Hhead[u] = h;
	for(int v : E[u])
		if(pre[u] != v)
		{
			if(dis[v] > dis[deep])
				deep = v;
		}
	for(int v : E[u])
		if(pre[u] != v)
		{
			Hpos[v] = (v == deep ? Hpos[u] + 1 : 1);
			decompose(v, (v == deep ? h : v));
		}
}

void addedge(int pos, int i)
{
	if(s[pos] && s[pos] != i)
		topo[s[pos]].emplace_back(i);
	if(e[pos] && e[pos] != i)
		topo[i].emplace_back(e[pos]);
}

bool isSubtree(int r, int c)
{
	return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

void solve()
{
	ts = 0, idx = 0;
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		pre[i] = dis[i] = s[i] = e[i] = Hhead[i] = Hsz[i] = Hpos[i] = 0;
		E[i].clear();
	}
	for(int i = 1; i < N; i++)
	{
		int u, v;
		cin >> u >> v;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	
	dfs(1);
	Hpos[1] = 1;
	decompose(1, 1);

	cin >> M;
	idx = M;
	
	for(int i = 1; i <= 6 * N; i++)
	{
		deg[i] = 0;
		topo[i].clear();
	}
	
	for(int i = 1; i <= N; i++)
		Hsz[Hhead[i]] = max(Hsz[Hhead[i]], Hpos[i]);
	
	hld.init();

	for(int i = 1; i <= M; i++)
	{
		cin >> fr[i] >> to[i];
		s[fr[i]] = i;
		e[to[i]] = i;
		hld.segInsert(hld.root[Hhead[fr[i]]][0], 1, Hsz[Hhead[fr[i]]], Hpos[fr[i]], i, 0);
		hld.segInsert(hld.root[Hhead[to[i]]][1], 1, Hsz[Hhead[to[i]]], Hpos[to[i]], i, 1);
	}
	for(int i = 1; i <= M; i++)
	{
		int u = fr[i], v = to[i];
		addedge(u, i);
		addedge(v, i);

		if(pre[u] == v || pre[v] == u) continue;

		int cancelUp = 1;
		
		if(isSubtree(u, v))
			v = pre[v];
		else if(isSubtree(v, u))
			u = pre[u];
		else
			u = pre[u], v = pre[v], cancelUp = 0;

		while(Hhead[u] != Hhead[v])
		{
			if(dis[Hhead[u]] < dis[Hhead[v]])
				swap(u, v);
			hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, 1, Hpos[u]);
			u = pre[Hhead[u]];
		}
		
		if(dis[u] > dis[v]) swap(u, v);

		hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, Hpos[u] + cancelUp, Hpos[v]);
	}

	for(int i = 1; i <= idx; i++)
		for(int j : topo[i])
		{	
			// cout << i << "->" << j << '\n';
			deg[j]++;
		}
	queue<int> q;
	for(int i = 1; i <= idx; i++)
		if(deg[i] == 0)
			q.emplace(i);

	for(int t = 1; t <= idx; t++)
	{
		if(q.empty())
		{
			cout << "No\n";
			return;
		}
		int u = q.front();
		q.pop();
		for(int v : topo[u])
		{
			deg[v]--;
			if(deg[v] == 0)
				q.emplace(v);
		}
	}
	cout << "Yes\n";
}



signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while(T--)
	{
		solve();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 216532 KB Output is correct
2 Correct 111 ms 216368 KB Output is correct
3 Correct 113 ms 216440 KB Output is correct
4 Correct 149 ms 216544 KB Output is correct
5 Correct 137 ms 216500 KB Output is correct
6 Correct 112 ms 216480 KB Output is correct
7 Correct 117 ms 216448 KB Output is correct
8 Correct 119 ms 216556 KB Output is correct
9 Correct 191 ms 218692 KB Output is correct
10 Correct 192 ms 256992 KB Output is correct
11 Correct 121 ms 216408 KB Output is correct
12 Correct 161 ms 216560 KB Output is correct
13 Correct 324 ms 263888 KB Output is correct
14 Correct 243 ms 264060 KB Output is correct
15 Correct 440 ms 269112 KB Output is correct
16 Correct 711 ms 286752 KB Output is correct
17 Correct 347 ms 273144 KB Output is correct
18 Correct 236 ms 265184 KB Output is correct
19 Correct 301 ms 270628 KB Output is correct
20 Correct 287 ms 270624 KB Output is correct
21 Correct 304 ms 271736 KB Output is correct
22 Correct 210 ms 260904 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 216452 KB Output is correct
2 Correct 128 ms 216388 KB Output is correct
3 Correct 116 ms 216492 KB Output is correct
4 Correct 116 ms 216520 KB Output is correct
5 Correct 112 ms 216492 KB Output is correct
6 Correct 123 ms 216444 KB Output is correct
7 Correct 142 ms 216576 KB Output is correct
8 Correct 111 ms 216524 KB Output is correct
9 Correct 119 ms 216512 KB Output is correct
10 Correct 121 ms 216524 KB Output is correct
11 Correct 117 ms 216440 KB Output is correct
12 Correct 125 ms 216428 KB Output is correct
13 Correct 116 ms 216524 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 216452 KB Output is correct
2 Correct 128 ms 216388 KB Output is correct
3 Correct 116 ms 216492 KB Output is correct
4 Correct 116 ms 216520 KB Output is correct
5 Correct 112 ms 216492 KB Output is correct
6 Correct 123 ms 216444 KB Output is correct
7 Correct 142 ms 216576 KB Output is correct
8 Correct 111 ms 216524 KB Output is correct
9 Correct 119 ms 216512 KB Output is correct
10 Correct 121 ms 216524 KB Output is correct
11 Correct 117 ms 216440 KB Output is correct
12 Correct 125 ms 216428 KB Output is correct
13 Correct 116 ms 216524 KB Output is correct
14 Correct 112 ms 216460 KB Output is correct
15 Correct 119 ms 216456 KB Output is correct
16 Correct 132 ms 216640 KB Output is correct
17 Correct 118 ms 216520 KB Output is correct
18 Correct 113 ms 216468 KB Output is correct
19 Correct 112 ms 216456 KB Output is correct
20 Correct 122 ms 216528 KB Output is correct
21 Correct 126 ms 216432 KB Output is correct
22 Correct 129 ms 216512 KB Output is correct
23 Correct 112 ms 216444 KB Output is correct
24 Correct 111 ms 216416 KB Output is correct
25 Correct 114 ms 216524 KB Output is correct
26 Correct 118 ms 216444 KB Output is correct
27 Correct 112 ms 216520 KB Output is correct
28 Correct 122 ms 216380 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 216452 KB Output is correct
2 Correct 128 ms 216388 KB Output is correct
3 Correct 116 ms 216492 KB Output is correct
4 Correct 116 ms 216520 KB Output is correct
5 Correct 112 ms 216492 KB Output is correct
6 Correct 123 ms 216444 KB Output is correct
7 Correct 142 ms 216576 KB Output is correct
8 Correct 111 ms 216524 KB Output is correct
9 Correct 119 ms 216512 KB Output is correct
10 Correct 121 ms 216524 KB Output is correct
11 Correct 117 ms 216440 KB Output is correct
12 Correct 125 ms 216428 KB Output is correct
13 Correct 116 ms 216524 KB Output is correct
14 Correct 112 ms 216460 KB Output is correct
15 Correct 119 ms 216456 KB Output is correct
16 Correct 132 ms 216640 KB Output is correct
17 Correct 118 ms 216520 KB Output is correct
18 Correct 113 ms 216468 KB Output is correct
19 Correct 112 ms 216456 KB Output is correct
20 Correct 122 ms 216528 KB Output is correct
21 Correct 126 ms 216432 KB Output is correct
22 Correct 129 ms 216512 KB Output is correct
23 Correct 112 ms 216444 KB Output is correct
24 Correct 111 ms 216416 KB Output is correct
25 Correct 114 ms 216524 KB Output is correct
26 Correct 118 ms 216444 KB Output is correct
27 Correct 112 ms 216520 KB Output is correct
28 Correct 122 ms 216380 KB Output is correct
29 Correct 121 ms 216556 KB Output is correct
30 Correct 115 ms 216616 KB Output is correct
31 Correct 119 ms 216576 KB Output is correct
32 Correct 120 ms 216528 KB Output is correct
33 Correct 112 ms 216468 KB Output is correct
34 Correct 138 ms 216544 KB Output is correct
35 Correct 130 ms 216652 KB Output is correct
36 Correct 113 ms 216428 KB Output is correct
37 Correct 112 ms 216540 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 216452 KB Output is correct
2 Correct 128 ms 216388 KB Output is correct
3 Correct 116 ms 216492 KB Output is correct
4 Correct 116 ms 216520 KB Output is correct
5 Correct 112 ms 216492 KB Output is correct
6 Correct 123 ms 216444 KB Output is correct
7 Correct 142 ms 216576 KB Output is correct
8 Correct 111 ms 216524 KB Output is correct
9 Correct 119 ms 216512 KB Output is correct
10 Correct 121 ms 216524 KB Output is correct
11 Correct 117 ms 216440 KB Output is correct
12 Correct 125 ms 216428 KB Output is correct
13 Correct 116 ms 216524 KB Output is correct
14 Correct 112 ms 216460 KB Output is correct
15 Correct 119 ms 216456 KB Output is correct
16 Correct 132 ms 216640 KB Output is correct
17 Correct 118 ms 216520 KB Output is correct
18 Correct 113 ms 216468 KB Output is correct
19 Correct 112 ms 216456 KB Output is correct
20 Correct 122 ms 216528 KB Output is correct
21 Correct 126 ms 216432 KB Output is correct
22 Correct 129 ms 216512 KB Output is correct
23 Correct 112 ms 216444 KB Output is correct
24 Correct 111 ms 216416 KB Output is correct
25 Correct 114 ms 216524 KB Output is correct
26 Correct 118 ms 216444 KB Output is correct
27 Correct 112 ms 216520 KB Output is correct
28 Correct 122 ms 216380 KB Output is correct
29 Correct 121 ms 216556 KB Output is correct
30 Correct 115 ms 216616 KB Output is correct
31 Correct 119 ms 216576 KB Output is correct
32 Correct 120 ms 216528 KB Output is correct
33 Correct 112 ms 216468 KB Output is correct
34 Correct 138 ms 216544 KB Output is correct
35 Correct 130 ms 216652 KB Output is correct
36 Correct 113 ms 216428 KB Output is correct
37 Correct 112 ms 216540 KB Output is correct
38 Correct 168 ms 218664 KB Output is correct
39 Correct 207 ms 256980 KB Output is correct
40 Correct 242 ms 227472 KB Output is correct
41 Correct 185 ms 218220 KB Output is correct
42 Correct 146 ms 218572 KB Output is correct
43 Correct 155 ms 218256 KB Output is correct
44 Correct 122 ms 216908 KB Output is correct
45 Correct 240 ms 241968 KB Output is correct
46 Correct 202 ms 241984 KB Output is correct
47 Correct 631 ms 288300 KB Output is correct
48 Correct 635 ms 289232 KB Output is correct
49 Correct 227 ms 244444 KB Output is correct
50 Correct 229 ms 244600 KB Output is correct
51 Correct 191 ms 243648 KB Output is correct
52 Correct 190 ms 243840 KB Output is correct
53 Correct 131 ms 218284 KB Output is correct
54 Correct 231 ms 240812 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 216528 KB Output is correct
2 Correct 124 ms 216456 KB Output is correct
3 Correct 123 ms 216420 KB Output is correct
4 Correct 116 ms 216396 KB Output is correct
5 Correct 129 ms 216468 KB Output is correct
6 Correct 137 ms 216536 KB Output is correct
7 Correct 130 ms 216504 KB Output is correct
8 Correct 114 ms 216432 KB Output is correct
9 Correct 116 ms 216556 KB Output is correct
10 Correct 118 ms 216456 KB Output is correct
11 Correct 140 ms 216396 KB Output is correct
12 Correct 116 ms 216420 KB Output is correct
13 Correct 136 ms 216528 KB Output is correct
14 Correct 160 ms 216516 KB Output is correct
15 Correct 152 ms 216536 KB Output is correct
16 Correct 236 ms 241196 KB Output is correct
17 Correct 350 ms 250920 KB Output is correct
18 Correct 571 ms 263532 KB Output is correct
19 Correct 280 ms 243208 KB Output is correct
20 Correct 257 ms 243532 KB Output is correct
21 Correct 298 ms 243532 KB Output is correct
22 Correct 357 ms 251344 KB Output is correct
23 Correct 373 ms 250892 KB Output is correct
24 Correct 336 ms 251456 KB Output is correct
25 Correct 325 ms 250908 KB Output is correct
26 Correct 318 ms 251136 KB Output is correct
27 Correct 318 ms 243652 KB Output is correct
28 Correct 286 ms 243640 KB Output is correct
29 Correct 289 ms 243756 KB Output is correct
30 Correct 305 ms 244688 KB Output is correct
31 Correct 303 ms 244688 KB Output is correct
32 Correct 360 ms 244648 KB Output is correct
33 Correct 287 ms 244728 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 216532 KB Output is correct
2 Correct 111 ms 216368 KB Output is correct
3 Correct 113 ms 216440 KB Output is correct
4 Correct 149 ms 216544 KB Output is correct
5 Correct 137 ms 216500 KB Output is correct
6 Correct 112 ms 216480 KB Output is correct
7 Correct 117 ms 216448 KB Output is correct
8 Correct 119 ms 216556 KB Output is correct
9 Correct 191 ms 218692 KB Output is correct
10 Correct 192 ms 256992 KB Output is correct
11 Correct 121 ms 216408 KB Output is correct
12 Correct 161 ms 216560 KB Output is correct
13 Correct 324 ms 263888 KB Output is correct
14 Correct 243 ms 264060 KB Output is correct
15 Correct 440 ms 269112 KB Output is correct
16 Correct 711 ms 286752 KB Output is correct
17 Correct 347 ms 273144 KB Output is correct
18 Correct 236 ms 265184 KB Output is correct
19 Correct 301 ms 270628 KB Output is correct
20 Correct 287 ms 270624 KB Output is correct
21 Correct 304 ms 271736 KB Output is correct
22 Correct 210 ms 260904 KB Output is correct
23 Correct 127 ms 216452 KB Output is correct
24 Correct 128 ms 216388 KB Output is correct
25 Correct 116 ms 216492 KB Output is correct
26 Correct 116 ms 216520 KB Output is correct
27 Correct 112 ms 216492 KB Output is correct
28 Correct 123 ms 216444 KB Output is correct
29 Correct 142 ms 216576 KB Output is correct
30 Correct 111 ms 216524 KB Output is correct
31 Correct 119 ms 216512 KB Output is correct
32 Correct 121 ms 216524 KB Output is correct
33 Correct 117 ms 216440 KB Output is correct
34 Correct 125 ms 216428 KB Output is correct
35 Correct 116 ms 216524 KB Output is correct
36 Correct 112 ms 216460 KB Output is correct
37 Correct 119 ms 216456 KB Output is correct
38 Correct 132 ms 216640 KB Output is correct
39 Correct 118 ms 216520 KB Output is correct
40 Correct 113 ms 216468 KB Output is correct
41 Correct 112 ms 216456 KB Output is correct
42 Correct 122 ms 216528 KB Output is correct
43 Correct 126 ms 216432 KB Output is correct
44 Correct 129 ms 216512 KB Output is correct
45 Correct 112 ms 216444 KB Output is correct
46 Correct 111 ms 216416 KB Output is correct
47 Correct 114 ms 216524 KB Output is correct
48 Correct 118 ms 216444 KB Output is correct
49 Correct 112 ms 216520 KB Output is correct
50 Correct 122 ms 216380 KB Output is correct
51 Correct 121 ms 216556 KB Output is correct
52 Correct 115 ms 216616 KB Output is correct
53 Correct 119 ms 216576 KB Output is correct
54 Correct 120 ms 216528 KB Output is correct
55 Correct 112 ms 216468 KB Output is correct
56 Correct 138 ms 216544 KB Output is correct
57 Correct 130 ms 216652 KB Output is correct
58 Correct 113 ms 216428 KB Output is correct
59 Correct 112 ms 216540 KB Output is correct
60 Correct 168 ms 218664 KB Output is correct
61 Correct 207 ms 256980 KB Output is correct
62 Correct 242 ms 227472 KB Output is correct
63 Correct 185 ms 218220 KB Output is correct
64 Correct 146 ms 218572 KB Output is correct
65 Correct 155 ms 218256 KB Output is correct
66 Correct 122 ms 216908 KB Output is correct
67 Correct 240 ms 241968 KB Output is correct
68 Correct 202 ms 241984 KB Output is correct
69 Correct 631 ms 288300 KB Output is correct
70 Correct 635 ms 289232 KB Output is correct
71 Correct 227 ms 244444 KB Output is correct
72 Correct 229 ms 244600 KB Output is correct
73 Correct 191 ms 243648 KB Output is correct
74 Correct 190 ms 243840 KB Output is correct
75 Correct 131 ms 218284 KB Output is correct
76 Correct 231 ms 240812 KB Output is correct
77 Correct 118 ms 216528 KB Output is correct
78 Correct 124 ms 216456 KB Output is correct
79 Correct 123 ms 216420 KB Output is correct
80 Correct 116 ms 216396 KB Output is correct
81 Correct 129 ms 216468 KB Output is correct
82 Correct 137 ms 216536 KB Output is correct
83 Correct 130 ms 216504 KB Output is correct
84 Correct 114 ms 216432 KB Output is correct
85 Correct 116 ms 216556 KB Output is correct
86 Correct 118 ms 216456 KB Output is correct
87 Correct 140 ms 216396 KB Output is correct
88 Correct 116 ms 216420 KB Output is correct
89 Correct 136 ms 216528 KB Output is correct
90 Correct 160 ms 216516 KB Output is correct
91 Correct 152 ms 216536 KB Output is correct
92 Correct 236 ms 241196 KB Output is correct
93 Correct 350 ms 250920 KB Output is correct
94 Correct 571 ms 263532 KB Output is correct
95 Correct 280 ms 243208 KB Output is correct
96 Correct 257 ms 243532 KB Output is correct
97 Correct 298 ms 243532 KB Output is correct
98 Correct 357 ms 251344 KB Output is correct
99 Correct 373 ms 250892 KB Output is correct
100 Correct 336 ms 251456 KB Output is correct
101 Correct 325 ms 250908 KB Output is correct
102 Correct 318 ms 251136 KB Output is correct
103 Correct 318 ms 243652 KB Output is correct
104 Correct 286 ms 243640 KB Output is correct
105 Correct 289 ms 243756 KB Output is correct
106 Correct 305 ms 244688 KB Output is correct
107 Correct 303 ms 244688 KB Output is correct
108 Correct 360 ms 244648 KB Output is correct
109 Correct 287 ms 244728 KB Output is correct
110 Correct 188 ms 216604 KB Output is correct
111 Correct 144 ms 216496 KB Output is correct
112 Execution timed out 5100 ms 756216 KB Time limit exceeded
113 Halted 0 ms 0 KB -