oj.uz

Submission #718815

# Submission time Handle Problem Language Result Execution time Memory
718815 2023-04-05T00:09:29 Z Abrar_Al_Samit Jail (JOI22_jail) C++17
72 / 100
 5000 ms 157912 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 120001;
const int lg = 17;

vector<int>g[nax], t[nax];
int n, m;

int bed[nax], work[nax];
int sp[nax][lg];
int tt = 0, st[nax], en[nax];
int vis[nax], dep[nax];
vector<int>wh[nax];

void dfs(int v, int p = 1, int d = 0) {
	dep[v] = d;
	sp[v][0] = p;
	st[v] = tt++;
	for(int j=1; j<lg; ++j) {
		sp[v][j] = sp[sp[v][j-1]][j-1];
	}
	for(int u : g[v]) if(u!=p) {
		dfs(u, v, d+1);
	}
	en[v] = tt-1;
}
bool anc(int u, int v) {
	return st[u] <= st[v] && en[u] >= en[v];
}
int LIFT(int u, int v) {
	for(int j=lg-1; j>=0; --j) if(!anc(sp[u][j], v)) {
		u = sp[u][j];
	}
	if(!anc(u, v)) u = sp[u][0];
	return u;
}
bool lies(int u, int v, int lca, int x) {
	if(anc(lca, x)) {
		return anc(x, u) || anc(x, v);
	}
	return false;
}
int bond(int i, int j) {
	int lca1 = LIFT(bed[i], work[i]);
	int lca2 = LIFT(bed[j], work[j]);
	int len1 = dep[bed[i]] + dep[work[i]] - 2 * dep[lca1];
	int len2 = dep[bed[j]] + dep[work[j]] - 2 * dep[lca2];

	bool spd = false;
	if(len1 < len2) {
		spd = true;
		swap(i, j);
		swap(len1, len2);
		swap(lca1, lca2);
	}


	bool f = lies(bed[i], work[i], lca1, bed[j]);
	bool ff = lies(bed[i], work[i], lca1, work[j]);

	if(f && ff) return 1;

	if(spd) {
		swap(i, j);
		swap(len1, len2);
		swap(lca1, lca2);

		f = lies(bed[i], work[i], lca1, bed[j]);
		ff = lies(bed[i], work[i], lca1, work[j]);
	}
	if(f) {
		t[j].push_back(i);
	}
	if(ff) {
		t[i].push_back(j);
	}
	return 0;
}

int go(int v) {
	vis[v] = 1;
	for(int u : t[v]) {
		if(!vis[u]) {
			if(go(u)) return 1;
		} else {
			if(vis[u]==1) return 1;
		}
	}
	vis[v] = 2;
	return 0;
}
void PlayGround() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		g[i].clear(), t[i].clear(), tt = vis[i] = 0;
		wh[i].clear();
	}
	for(int i=0; i<n-1; ++i) {
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);

	cin>>m;
	for(int i=1; i<=m; ++i) {
		cin>>bed[i]>>work[i];
		wh[bed[i]].push_back(i);
		wh[work[i]].push_back(i);
	}



	for(int i=1; i<=m; ++i) {
		int lca = LIFT(bed[i], work[i]);
		int x = bed[i], y = work[i];
		while(1) {
			for(int z : wh[x]) if(z!=i) {
				if(bond(i, z)) {
					cout<<"No\n";
					return;
				}
			}
			if(x==lca) break;
			x = sp[x][0];
		}
		while(1) {
			for(int z : wh[y]) if(z!=i) {
				if(bond(i, z)) {
					cout<<"No\n";
					return;
				}
			}
			if(y==lca) break;
			y = sp[y][0];
		}
	}

	for(int i=1; i<=m; ++i) if(!vis[i]) {
		if(go(i)) {
			cout<<"No\n";
			return;
		}
	}
	cout<<"Yes\n";

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin>>tc;
	while(tc--) {
		PlayGround();
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8768 KB Output is correct
3 Correct 5 ms 8788 KB Output is correct
4 Correct 15 ms 8836 KB Output is correct
5 Correct 26 ms 8836 KB Output is correct
6 Correct 6 ms 8788 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 10 ms 8868 KB Output is correct
9 Correct 179 ms 11424 KB Output is correct
10 Correct 624 ms 31228 KB Output is correct
11 Correct 9 ms 8788 KB Output is correct
12 Correct 37 ms 8840 KB Output is correct
13 Correct 1346 ms 63124 KB Output is correct
14 Correct 82 ms 35764 KB Output is correct
15 Correct 81 ms 34816 KB Output is correct
16 Correct 130 ms 37440 KB Output is correct
17 Execution timed out 5047 ms 157912 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8812 KB Output is correct
3 Correct 8 ms 8852 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8852 KB Output is correct
6 Correct 5 ms 8788 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 6 ms 8788 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 7 ms 8844 KB Output is correct
13 Correct 5 ms 8788 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8812 KB Output is correct
3 Correct 8 ms 8852 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8852 KB Output is correct
6 Correct 5 ms 8788 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 6 ms 8788 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 7 ms 8844 KB Output is correct
13 Correct 5 ms 8788 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 8788 KB Output is correct
16 Correct 6 ms 8788 KB Output is correct
17 Correct 5 ms 8788 KB Output is correct
18 Correct 6 ms 8788 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 5 ms 8788 KB Output is correct
22 Correct 5 ms 8788 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 4 ms 8788 KB Output is correct
25 Correct 6 ms 8788 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8852 KB Output is correct
28 Correct 5 ms 8788 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8812 KB Output is correct
3 Correct 8 ms 8852 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8852 KB Output is correct
6 Correct 5 ms 8788 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 6 ms 8788 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 7 ms 8844 KB Output is correct
13 Correct 5 ms 8788 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 8788 KB Output is correct
16 Correct 6 ms 8788 KB Output is correct
17 Correct 5 ms 8788 KB Output is correct
18 Correct 6 ms 8788 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 5 ms 8788 KB Output is correct
22 Correct 5 ms 8788 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 4 ms 8788 KB Output is correct
25 Correct 6 ms 8788 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8852 KB Output is correct
28 Correct 5 ms 8788 KB Output is correct
29 Correct 10 ms 8916 KB Output is correct
30 Correct 6 ms 8852 KB Output is correct
31 Correct 6 ms 8852 KB Output is correct
32 Correct 6 ms 8856 KB Output is correct
33 Correct 6 ms 8788 KB Output is correct
34 Correct 9 ms 8844 KB Output is correct
35 Correct 13 ms 8868 KB Output is correct
36 Correct 6 ms 8788 KB Output is correct
37 Correct 7 ms 8788 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8812 KB Output is correct
3 Correct 8 ms 8852 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8852 KB Output is correct
6 Correct 5 ms 8788 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 6 ms 8788 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 7 ms 8844 KB Output is correct
13 Correct 5 ms 8788 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 8788 KB Output is correct
16 Correct 6 ms 8788 KB Output is correct
17 Correct 5 ms 8788 KB Output is correct
18 Correct 6 ms 8788 KB Output is correct
19 Correct 5 ms 8788 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 5 ms 8788 KB Output is correct
22 Correct 5 ms 8788 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 4 ms 8788 KB Output is correct
25 Correct 6 ms 8788 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8852 KB Output is correct
28 Correct 5 ms 8788 KB Output is correct
29 Correct 10 ms 8916 KB Output is correct
30 Correct 6 ms 8852 KB Output is correct
31 Correct 6 ms 8852 KB Output is correct
32 Correct 6 ms 8856 KB Output is correct
33 Correct 6 ms 8788 KB Output is correct
34 Correct 9 ms 8844 KB Output is correct
35 Correct 13 ms 8868 KB Output is correct
36 Correct 6 ms 8788 KB Output is correct
37 Correct 7 ms 8788 KB Output is correct
38 Correct 192 ms 11340 KB Output is correct
39 Correct 604 ms 31332 KB Output is correct
40 Correct 53 ms 9816 KB Output is correct
41 Correct 38 ms 9660 KB Output is correct
42 Correct 34 ms 10064 KB Output is correct
43 Correct 28 ms 9684 KB Output is correct
44 Correct 24 ms 9068 KB Output is correct
45 Correct 74 ms 22428 KB Output is correct
46 Correct 74 ms 22428 KB Output is correct
47 Correct 163 ms 26080 KB Output is correct
48 Correct 158 ms 26184 KB Output is correct
49 Correct 56 ms 22584 KB Output is correct
50 Correct 72 ms 22740 KB Output is correct
51 Correct 70 ms 23580 KB Output is correct
52 Correct 51 ms 23596 KB Output is correct
53 Correct 19 ms 9864 KB Output is correct
54 Correct 90 ms 22388 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 5 ms 8728 KB Output is correct
3 Correct 5 ms 8788 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 10 ms 8724 KB Output is correct
6 Correct 5 ms 8788 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 4 ms 8788 KB Output is correct
9 Correct 4 ms 8788 KB Output is correct
10 Correct 5 ms 8788 KB Output is correct
11 Correct 5 ms 8788 KB Output is correct
12 Correct 6 ms 8788 KB Output is correct
13 Correct 22 ms 8788 KB Output is correct
14 Correct 37 ms 8844 KB Output is correct
15 Correct 55 ms 8844 KB Output is correct
16 Correct 125 ms 23540 KB Output is correct
17 Correct 102 ms 28100 KB Output is correct
18 Correct 149 ms 30708 KB Output is correct
19 Correct 121 ms 25628 KB Output is correct
20 Correct 80 ms 25380 KB Output is correct
21 Correct 103 ms 25664 KB Output is correct
22 Correct 114 ms 29228 KB Output is correct
23 Correct 98 ms 28840 KB Output is correct
24 Correct 346 ms 34864 KB Output is correct
25 Correct 218 ms 31940 KB Output is correct
26 Correct 344 ms 35048 KB Output is correct
27 Correct 280 ms 35556 KB Output is correct
28 Correct 272 ms 39756 KB Output is correct
29 Correct 285 ms 36804 KB Output is correct
30 Correct 161 ms 33096 KB Output is correct
31 Correct 147 ms 33604 KB Output is correct
32 Correct 154 ms 32328 KB Output is correct
33 Correct 164 ms 33628 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8768 KB Output is correct
3 Correct 5 ms 8788 KB Output is correct
4 Correct 15 ms 8836 KB Output is correct
5 Correct 26 ms 8836 KB Output is correct
6 Correct 6 ms 8788 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 10 ms 8868 KB Output is correct
9 Correct 179 ms 11424 KB Output is correct
10 Correct 624 ms 31228 KB Output is correct
11 Correct 9 ms 8788 KB Output is correct
12 Correct 37 ms 8840 KB Output is correct
13 Correct 1346 ms 63124 KB Output is correct
14 Correct 82 ms 35764 KB Output is correct
15 Correct 81 ms 34816 KB Output is correct
16 Correct 130 ms 37440 KB Output is correct
17 Execution timed out 5047 ms 157912 KB Time limit exceeded
18 Halted 0 ms 0 KB -