oj.uz

답안 #727034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727034 2023-04-19T20:53:26 Z dozer Jail (JOI22_jail) C++14
5 / 100
 5000 ms 31924 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(), 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -