Submission #727034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
727034	2023-04-19T20:53:26 Z	dozer	Jail (JOI22_jail)	C++14	5 / 100	5000 ms	31924 KB

jail

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define LOGN 18


vector<int> adj[N], adj2[N];
int tin[N], tout[N], s[N], t[N], par[LOGN][N];
int cntr, dep[N], deg[N], ind[N];


void dfs(int node, int root, int d)
{
	tin[node] = cntr++;
	dep[node] = d;
	par[0][node] = root;
	for (auto i : adj[node])
		if (i != root) dfs(i, node, d + 1);
	tout[node] = cntr++;
}

bool ancestor(int a, int b)
{
	return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b)
{
	for (int i = LOGN - 1; i >= 0; i--)
	{
		if ((1<<i) < dep[a] && !ancestor(par[i][a], b)) a = par[i][a];
	}
	if (!ancestor(a, b)) a = par[0][a];
	return a;
}

bool intersects(int x, int a, int b)
{
	int l = lca(a, b);
	if (x == l) return 1;
	return (ancestor(x, a) ^ ancestor(x, b));
}


int32_t main()
{
	fastio();


	int q;
	cin>>q;
	while(q--)
	{
		int n, m;
		cin>>n;
		for (int i = 1; i <= n; i++)
			adj[i].clear(), ind[i] = 0;
		for (int i = 1; i < n; i++)
		{
			int u, v;
			cin>>u>>v;
			adj[u].pb(v);
			adj[v].pb(u);
		}

		cntr = 0;
		dfs(1, 0, 0);
		for (int i = 1; i < LOGN; i++)
		{
			for (int j = 1; j <= n; j++)
				par[i][j] = par[i - 1][par[i - 1][j]];
		}
		vector<pii> v;
		cin>>m;
		for (int i = 1; i <= m; i++)
			adj2[i].clear(), deg[i] = 0;

		for (int i = 1; i <= m; i++)
		{
			cin>>s[i]>>t[i];
			ind[s[i]] = i;
		}

		int flag = 0;
		for (int i = 1; i <= m; i++)
		{
			for (int j = i + 1; j <= m; j++)
			{
				int a = 0, b = 0;
				if (intersects(s[i], s[j], t[j]) || intersects(t[j], s[i], t[i])) a = 1;
				if (intersects(t[i], s[j], t[j]) || intersects(s[j], s[i], t[i])) b = 1;
				if (a && b) flag = 1;
			}
		}

		for (int i = 1; i <= m; i++)
		{
			int to = ind[t[i]];
			if (to != 0 && to != i)
			{
				deg[i]++;
				adj2[to].pb(i);			
			}
		}

		vector<int> done(m + 5, 0);

		queue<int> q;
		for (int i = 1; i <= m; i++)
			if (deg[i] == 0) q.push(i);

		while(!q.empty())
		{
			int top = q.front();
			q.pop();
			done[top] = 1;
			for (auto i : adj2[top])
			{
				deg[i]--;
				if (deg[i] == 0) q.push(i);
			}
		} 
		for (int i = 1; i <= m; i++)
			if (done[i] == 0) flag = 1;

		if (flag) cout<<"No\n";
		else cout<<"Yes\n";
	}



	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9812 KB	Output is correct
2	Correct	7 ms	9812 KB	Output is correct
3	Correct	5 ms	9812 KB	Output is correct
4	Correct	18 ms	9812 KB	Output is correct
5	Correct	24 ms	9812 KB	Output is correct
6	Correct	7 ms	9812 KB	Output is correct
7	Correct	6 ms	9812 KB	Output is correct
8	Correct	16 ms	9812 KB	Output is correct
9	Correct	467 ms	10928 KB	Output is correct
10	Correct	53 ms	31420 KB	Output is correct
11	Correct	12 ms	9784 KB	Output is correct
12	Correct	131 ms	9868 KB	Output is correct
13	Execution timed out	5057 ms	31924 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	6 ms	9812 KB	Output is correct
5	Correct	7 ms	9812 KB	Output is correct
6	Correct	6 ms	9884 KB	Output is correct
7	Correct	7 ms	9812 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9812 KB	Output is correct
10	Correct	8 ms	9812 KB	Output is correct
11	Correct	6 ms	9812 KB	Output is correct
12	Correct	6 ms	9804 KB	Output is correct
13	Correct	5 ms	9812 KB	Output is correct

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	6 ms	9812 KB	Output is correct
5	Correct	7 ms	9812 KB	Output is correct
6	Correct	6 ms	9884 KB	Output is correct
7	Correct	7 ms	9812 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9812 KB	Output is correct
10	Correct	8 ms	9812 KB	Output is correct
11	Correct	6 ms	9812 KB	Output is correct
12	Correct	6 ms	9804 KB	Output is correct
13	Correct	5 ms	9812 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	6 ms	9856 KB	Output is correct
16	Correct	6 ms	9812 KB	Output is correct
17	Correct	8 ms	9860 KB	Output is correct
18	Correct	7 ms	9864 KB	Output is correct
19	Correct	6 ms	9812 KB	Output is correct
20	Correct	6 ms	9812 KB	Output is correct
21	Correct	7 ms	9868 KB	Output is correct
22	Correct	7 ms	9900 KB	Output is correct
23	Correct	6 ms	9812 KB	Output is correct
24	Incorrect	6 ms	9812 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #4
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	6 ms	9812 KB	Output is correct
5	Correct	7 ms	9812 KB	Output is correct
6	Correct	6 ms	9884 KB	Output is correct
7	Correct	7 ms	9812 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9812 KB	Output is correct
10	Correct	8 ms	9812 KB	Output is correct
11	Correct	6 ms	9812 KB	Output is correct
12	Correct	6 ms	9804 KB	Output is correct
13	Correct	5 ms	9812 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	6 ms	9856 KB	Output is correct
16	Correct	6 ms	9812 KB	Output is correct
17	Correct	8 ms	9860 KB	Output is correct
18	Correct	7 ms	9864 KB	Output is correct
19	Correct	6 ms	9812 KB	Output is correct
20	Correct	6 ms	9812 KB	Output is correct
21	Correct	7 ms	9868 KB	Output is correct
22	Correct	7 ms	9900 KB	Output is correct
23	Correct	6 ms	9812 KB	Output is correct
24	Incorrect	6 ms	9812 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	6 ms	9812 KB	Output is correct
5	Correct	7 ms	9812 KB	Output is correct
6	Correct	6 ms	9884 KB	Output is correct
7	Correct	7 ms	9812 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9812 KB	Output is correct
10	Correct	8 ms	9812 KB	Output is correct
11	Correct	6 ms	9812 KB	Output is correct
12	Correct	6 ms	9804 KB	Output is correct
13	Correct	5 ms	9812 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	6 ms	9856 KB	Output is correct
16	Correct	6 ms	9812 KB	Output is correct
17	Correct	8 ms	9860 KB	Output is correct
18	Correct	7 ms	9864 KB	Output is correct
19	Correct	6 ms	9812 KB	Output is correct
20	Correct	6 ms	9812 KB	Output is correct
21	Correct	7 ms	9868 KB	Output is correct
22	Correct	7 ms	9900 KB	Output is correct
23	Correct	6 ms	9812 KB	Output is correct
24	Incorrect	6 ms	9812 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9808 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	11 ms	9864 KB	Output is correct
6	Correct	6 ms	9864 KB	Output is correct
7	Correct	6 ms	9812 KB	Output is correct
8	Correct	6 ms	9840 KB	Output is correct
9	Correct	6 ms	9820 KB	Output is correct
10	Incorrect	6 ms	9852 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9812 KB	Output is correct
2	Correct	7 ms	9812 KB	Output is correct
3	Correct	5 ms	9812 KB	Output is correct
4	Correct	18 ms	9812 KB	Output is correct
5	Correct	24 ms	9812 KB	Output is correct
6	Correct	7 ms	9812 KB	Output is correct
7	Correct	6 ms	9812 KB	Output is correct
8	Correct	16 ms	9812 KB	Output is correct
9	Correct	467 ms	10928 KB	Output is correct
10	Correct	53 ms	31420 KB	Output is correct
11	Correct	12 ms	9784 KB	Output is correct
12	Correct	131 ms	9868 KB	Output is correct
13	Execution timed out	5057 ms	31924 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Submission #727034

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 16.0

Subtask #4 0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 16.0

Subtask #4
0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0