oj.uz

Submission #727030

# Submission time Handle Problem Language Result Execution time Memory
727030 2023-04-19T20:48:15 Z dozer Jail (JOI22_jail) C++14
5 / 100
 5000 ms 33996 KB 
#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();
		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)
			{
				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++)
			flag |= (1 - done[i]);
*/
		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 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 13 ms 9756 KB Output is correct
5 Correct 35 ms 10488 KB Output is correct
6 Correct 6 ms 9900 KB Output is correct
7 Correct 8 ms 9932 KB Output is correct
8 Correct 24 ms 9884 KB Output is correct
9 Correct 456 ms 12048 KB Output is correct
10 Correct 68 ms 32312 KB Output is correct
11 Correct 16 ms 9940 KB Output is correct
12 Correct 138 ms 10736 KB Output is correct
13 Execution timed out 5063 ms 33996 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 8 ms 9892 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9864 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 7 ms 9916 KB Output is correct
11 Correct 6 ms 9872 KB Output is correct
12 Correct 5 ms 9812 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 6 ms 9812 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 8 ms 9892 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9864 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 7 ms 9916 KB Output is correct
11 Correct 6 ms 9872 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9812 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 8 ms 9892 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9864 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 7 ms 9916 KB Output is correct
11 Correct 6 ms 9872 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9812 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 8 ms 9892 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9864 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 7 ms 9916 KB Output is correct
11 Correct 6 ms 9872 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9812 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Incorrect 7 ms 9812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.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 13 ms 9756 KB Output is correct
5 Correct 35 ms 10488 KB Output is correct
6 Correct 6 ms 9900 KB Output is correct
7 Correct 8 ms 9932 KB Output is correct
8 Correct 24 ms 9884 KB Output is correct
9 Correct 456 ms 12048 KB Output is correct
10 Correct 68 ms 32312 KB Output is correct
11 Correct 16 ms 9940 KB Output is correct
12 Correct 138 ms 10736 KB Output is correct
13 Execution timed out 5063 ms 33996 KB Time limit exceeded
14 Halted 0 ms 0 KB -