oj.uz

Submission #680764

# Submission time Handle Problem Language Result Execution time Memory
680764 2023-01-11T18:06:09 Z arnold518 Jail (JOI22_jail) C++17
72 / 100
 5000 ms 418704 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int Q, N, M;
vector<int> adj[MAXN+10];
pii A[MAXN+10];
vector<int> S[MAXN+10], E[MAXN+10];
int dep[MAXN+10], par[MAXN+10];

vector<int> adj2[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	par[now]=bef;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
}

int vis[MAXN+10];
bool dfs2(int now)
{
	vis[now]=1;
	for(int nxt : adj2[now])
	{
		if(vis[nxt]==1) return true;
		if(vis[nxt]==0 && dfs2(nxt)) return true;
	}
	vis[now]=2;
	return false;
}

bool solve()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	scanf("%d", &M);
	for(int i=1; i<=M; i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
		S[A[i].first].push_back(i);
		E[A[i].second].push_back(i);
	}

	dfs(1, 0, 1);

	for(int i=1; i<=M; i++)
	{
		int u=A[i].first, v=A[i].second;
		while(1)
		{
			if(dep[u]>dep[v]) swap(u, v);
			for(auto it : S[v]) if(it!=i) adj2[it].push_back(i);
			for(auto it : E[v]) if(it!=i) adj2[i].push_back(it);
			if(u==v) break;
			v=par[v];
		}
	}

	for(int i=1; i<=M; i++)
	{
		if(vis[i]) continue;
		if(dfs2(i)) return false;
	}
	return true;
}

void clear()
{
	for(int i=1; i<=N; i++)
	{
		adj[i].clear();
		S[i].clear(); E[i].clear();
	}
	for(int i=1; i<=M; i++)
	{
		adj2[i].clear();
		vis[i]=0;
	}
}

int main()
{
	scanf("%d", &Q);
	while(Q--)
	{
		if(solve()) printf("Yes\n");
		else printf("No\n");
		clear();
	}
}

Compilation message

jail.cpp: In function 'bool solve()':
jail.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
jail.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
jail.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 9 ms 19084 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 21 ms 19548 KB Output is correct
5 Correct 28 ms 19760 KB Output is correct
6 Correct 14 ms 19156 KB Output is correct
7 Correct 11 ms 19128 KB Output is correct
8 Correct 12 ms 19284 KB Output is correct
9 Correct 99 ms 23016 KB Output is correct
10 Correct 231 ms 29876 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 46 ms 20100 KB Output is correct
13 Correct 149 ms 62532 KB Output is correct
14 Correct 186 ms 76488 KB Output is correct
15 Execution timed out 5060 ms 418704 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 10 ms 19112 KB Output is correct
3 Correct 10 ms 19124 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19164 KB Output is correct
6 Correct 11 ms 19124 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 10 ms 19124 KB Output is correct
11 Correct 11 ms 19076 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 13 ms 19128 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 10 ms 19112 KB Output is correct
3 Correct 10 ms 19124 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19164 KB Output is correct
6 Correct 11 ms 19124 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 10 ms 19124 KB Output is correct
11 Correct 11 ms 19076 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 13 ms 19128 KB Output is correct
14 Correct 10 ms 19100 KB Output is correct
15 Correct 9 ms 19028 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 11 ms 19124 KB Output is correct
18 Correct 11 ms 19156 KB Output is correct
19 Correct 10 ms 19112 KB Output is correct
20 Correct 12 ms 19124 KB Output is correct
21 Correct 13 ms 19116 KB Output is correct
22 Correct 11 ms 19132 KB Output is correct
23 Correct 12 ms 19028 KB Output is correct
24 Correct 10 ms 19076 KB Output is correct
25 Correct 13 ms 19244 KB Output is correct
26 Correct 12 ms 19100 KB Output is correct
27 Correct 11 ms 19128 KB Output is correct
28 Correct 10 ms 19112 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 10 ms 19112 KB Output is correct
3 Correct 10 ms 19124 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19164 KB Output is correct
6 Correct 11 ms 19124 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 10 ms 19124 KB Output is correct
11 Correct 11 ms 19076 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 13 ms 19128 KB Output is correct
14 Correct 10 ms 19100 KB Output is correct
15 Correct 9 ms 19028 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 11 ms 19124 KB Output is correct
18 Correct 11 ms 19156 KB Output is correct
19 Correct 10 ms 19112 KB Output is correct
20 Correct 12 ms 19124 KB Output is correct
21 Correct 13 ms 19116 KB Output is correct
22 Correct 11 ms 19132 KB Output is correct
23 Correct 12 ms 19028 KB Output is correct
24 Correct 10 ms 19076 KB Output is correct
25 Correct 13 ms 19244 KB Output is correct
26 Correct 12 ms 19100 KB Output is correct
27 Correct 11 ms 19128 KB Output is correct
28 Correct 10 ms 19112 KB Output is correct
29 Correct 12 ms 19284 KB Output is correct
30 Correct 10 ms 19124 KB Output is correct
31 Correct 10 ms 19124 KB Output is correct
32 Correct 10 ms 19156 KB Output is correct
33 Correct 11 ms 19092 KB Output is correct
34 Correct 12 ms 19196 KB Output is correct
35 Correct 12 ms 19236 KB Output is correct
36 Correct 11 ms 19156 KB Output is correct
37 Correct 10 ms 19176 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 10 ms 19112 KB Output is correct
3 Correct 10 ms 19124 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19164 KB Output is correct
6 Correct 11 ms 19124 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 10 ms 19124 KB Output is correct
11 Correct 11 ms 19076 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 13 ms 19128 KB Output is correct
14 Correct 10 ms 19100 KB Output is correct
15 Correct 9 ms 19028 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 11 ms 19124 KB Output is correct
18 Correct 11 ms 19156 KB Output is correct
19 Correct 10 ms 19112 KB Output is correct
20 Correct 12 ms 19124 KB Output is correct
21 Correct 13 ms 19116 KB Output is correct
22 Correct 11 ms 19132 KB Output is correct
23 Correct 12 ms 19028 KB Output is correct
24 Correct 10 ms 19076 KB Output is correct
25 Correct 13 ms 19244 KB Output is correct
26 Correct 12 ms 19100 KB Output is correct
27 Correct 11 ms 19128 KB Output is correct
28 Correct 10 ms 19112 KB Output is correct
29 Correct 12 ms 19284 KB Output is correct
30 Correct 10 ms 19124 KB Output is correct
31 Correct 10 ms 19124 KB Output is correct
32 Correct 10 ms 19156 KB Output is correct
33 Correct 11 ms 19092 KB Output is correct
34 Correct 12 ms 19196 KB Output is correct
35 Correct 12 ms 19236 KB Output is correct
36 Correct 11 ms 19156 KB Output is correct
37 Correct 10 ms 19176 KB Output is correct
38 Correct 92 ms 22840 KB Output is correct
39 Correct 213 ms 29860 KB Output is correct
40 Correct 63 ms 21924 KB Output is correct
41 Correct 41 ms 20784 KB Output is correct
42 Correct 55 ms 22004 KB Output is correct
43 Correct 38 ms 20580 KB Output is correct
44 Correct 19 ms 19512 KB Output is correct
45 Correct 60 ms 25252 KB Output is correct
46 Correct 60 ms 25412 KB Output is correct
47 Correct 74 ms 26824 KB Output is correct
48 Correct 80 ms 26844 KB Output is correct
49 Correct 65 ms 25360 KB Output is correct
50 Correct 57 ms 25316 KB Output is correct
51 Correct 49 ms 25804 KB Output is correct
52 Correct 47 ms 25804 KB Output is correct
53 Correct 19 ms 19796 KB Output is correct
54 Correct 81 ms 25140 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 18996 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19112 KB Output is correct
5 Correct 17 ms 19292 KB Output is correct
6 Correct 10 ms 19048 KB Output is correct
7 Correct 10 ms 19112 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 12 ms 19088 KB Output is correct
11 Correct 12 ms 19088 KB Output is correct
12 Correct 12 ms 19156 KB Output is correct
13 Correct 27 ms 19664 KB Output is correct
14 Correct 34 ms 19916 KB Output is correct
15 Correct 31 ms 19768 KB Output is correct
16 Correct 66 ms 26420 KB Output is correct
17 Correct 164 ms 35824 KB Output is correct
18 Correct 488 ms 59796 KB Output is correct
19 Correct 72 ms 27264 KB Output is correct
20 Correct 77 ms 27312 KB Output is correct
21 Correct 68 ms 27264 KB Output is correct
22 Correct 130 ms 36256 KB Output is correct
23 Correct 120 ms 36788 KB Output is correct
24 Correct 148 ms 36320 KB Output is correct
25 Correct 116 ms 36352 KB Output is correct
26 Correct 126 ms 36480 KB Output is correct
27 Correct 239 ms 41316 KB Output is correct
28 Correct 191 ms 45380 KB Output is correct
29 Correct 214 ms 42404 KB Output is correct
30 Correct 103 ms 34712 KB Output is correct
31 Correct 109 ms 35248 KB Output is correct
32 Correct 133 ms 33896 KB Output is correct
33 Correct 167 ms 35268 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 9 ms 19084 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 21 ms 19548 KB Output is correct
5 Correct 28 ms 19760 KB Output is correct
6 Correct 14 ms 19156 KB Output is correct
7 Correct 11 ms 19128 KB Output is correct
8 Correct 12 ms 19284 KB Output is correct
9 Correct 99 ms 23016 KB Output is correct
10 Correct 231 ms 29876 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 46 ms 20100 KB Output is correct
13 Correct 149 ms 62532 KB Output is correct
14 Correct 186 ms 76488 KB Output is correct
15 Execution timed out 5060 ms 418704 KB Time limit exceeded
16 Halted 0 ms 0 KB -