oj.uz

Submission #741149

# Submission time Handle Problem Language Result Execution time Memory
741149 2023-05-13T16:11:01 Z Dan4Life Jail (JOI22_jail) C++17
49 / 100
 5000 ms 785092 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
const int mxN = (int)1.2e5+10;
const int mxM = (int)510;
int n, m, Cycle;
int ind[mxN], dis[mxM*2][mxN];
int s[mxM], t[mxM], vis[mxM];
vector<int> adj[mxN], adj2[mxM];

void dfs(int s, int p, int i){
	if(p==-1) dis[i][s] = 0;
	else dis[i][s] = dis[i][p]+1;
	for(auto u : adj[s])
		if(u!=p) dfs(u,s,i);
}

bool inPath(int x, int s, int t){
	return (dis[ind[s]][x]+dis[ind[t]][x]==dis[ind[s]][t]);
}

void dfs2(int s){
	vis[s]=1;
	for(auto u : adj2[s]){
		if(!vis[u]) dfs2(u);
		else if(vis[u]==1) { Cycle=1; return; }
	}
	vis[s]=2;
}

void solve(){
	cin >> n; Cycle = 0;
	for(int i = 1; i <= n; i++) adj[i].clear();
	for(int i = 0; i < m; i++) adj2[i].clear();
	for(int i = 0; i < n-1; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) dfs(i,-1,i);
	for(int i = 0; i < m; i++) vis[i]=0;
	cin >> m;
	vector<int> v; v.clear();
	for(int i = 0; i < m; i++) 
		cin >> s[i] >> t[i], v.pb(s[i]), v.pb(t[i]);
	sort(all(v)); v.erase(unique(all(v)),end(v));
	for(int i = 0; auto u : v) ind[u]=i, dfs(u,-1,i), i++;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			if(i!=j and inPath(s[j],s[i],t[i])) adj2[j].pb(i);
			if(i!=j and inPath(t[j],s[i],t[i])) adj2[i].pb(j);
		}
	}
	for(int i = 0; i < m; i++) if(!vis[i]) dfs2(i);
	cout << (!Cycle?"Yes":"No") << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t = 1; cin >> t; while(t--) solve();
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:50:17: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   50 |  for(int i = 0; auto u : v) ind[u]=i, dfs(u,-1,i), i++;
      |                 ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 55 ms 3980 KB Output is correct
5 Correct 111 ms 4684 KB Output is correct
6 Correct 11 ms 5176 KB Output is correct
7 Correct 13 ms 5076 KB Output is correct
8 Correct 20 ms 5336 KB Output is correct
9 Runtime error 107 ms 89188 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 12 ms 5124 KB Output is correct
4 Correct 12 ms 5168 KB Output is correct
5 Correct 14 ms 5176 KB Output is correct
6 Correct 13 ms 5172 KB Output is correct
7 Correct 13 ms 5172 KB Output is correct
8 Correct 13 ms 5092 KB Output is correct
9 Correct 12 ms 5172 KB Output is correct
10 Correct 15 ms 5076 KB Output is correct
11 Correct 12 ms 5220 KB Output is correct
12 Correct 6 ms 5076 KB Output is correct
13 Correct 7 ms 5076 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 12 ms 5124 KB Output is correct
4 Correct 12 ms 5168 KB Output is correct
5 Correct 14 ms 5176 KB Output is correct
6 Correct 13 ms 5172 KB Output is correct
7 Correct 13 ms 5172 KB Output is correct
8 Correct 13 ms 5092 KB Output is correct
9 Correct 12 ms 5172 KB Output is correct
10 Correct 15 ms 5076 KB Output is correct
11 Correct 12 ms 5220 KB Output is correct
12 Correct 6 ms 5076 KB Output is correct
13 Correct 7 ms 5076 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 13 ms 5092 KB Output is correct
17 Correct 12 ms 5076 KB Output is correct
18 Correct 13 ms 5172 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 13 ms 5076 KB Output is correct
21 Correct 13 ms 5088 KB Output is correct
22 Correct 11 ms 5092 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 3 ms 4052 KB Output is correct
25 Correct 15 ms 5076 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 12 ms 5076 KB Output is correct
28 Correct 2 ms 3284 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 12 ms 5124 KB Output is correct
4 Correct 12 ms 5168 KB Output is correct
5 Correct 14 ms 5176 KB Output is correct
6 Correct 13 ms 5172 KB Output is correct
7 Correct 13 ms 5172 KB Output is correct
8 Correct 13 ms 5092 KB Output is correct
9 Correct 12 ms 5172 KB Output is correct
10 Correct 15 ms 5076 KB Output is correct
11 Correct 12 ms 5220 KB Output is correct
12 Correct 6 ms 5076 KB Output is correct
13 Correct 7 ms 5076 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 13 ms 5092 KB Output is correct
17 Correct 12 ms 5076 KB Output is correct
18 Correct 13 ms 5172 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 13 ms 5076 KB Output is correct
21 Correct 13 ms 5088 KB Output is correct
22 Correct 11 ms 5092 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 3 ms 4052 KB Output is correct
25 Correct 15 ms 5076 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 12 ms 5076 KB Output is correct
28 Correct 2 ms 3284 KB Output is correct
29 Correct 20 ms 5332 KB Output is correct
30 Correct 17 ms 5204 KB Output is correct
31 Correct 17 ms 5236 KB Output is correct
32 Correct 15 ms 5092 KB Output is correct
33 Correct 14 ms 5076 KB Output is correct
34 Correct 15 ms 4704 KB Output is correct
35 Correct 16 ms 4820 KB Output is correct
36 Correct 12 ms 4740 KB Output is correct
37 Correct 9 ms 4704 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 12 ms 5124 KB Output is correct
4 Correct 12 ms 5168 KB Output is correct
5 Correct 14 ms 5176 KB Output is correct
6 Correct 13 ms 5172 KB Output is correct
7 Correct 13 ms 5172 KB Output is correct
8 Correct 13 ms 5092 KB Output is correct
9 Correct 12 ms 5172 KB Output is correct
10 Correct 15 ms 5076 KB Output is correct
11 Correct 12 ms 5220 KB Output is correct
12 Correct 6 ms 5076 KB Output is correct
13 Correct 7 ms 5076 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 13 ms 5092 KB Output is correct
17 Correct 12 ms 5076 KB Output is correct
18 Correct 13 ms 5172 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 13 ms 5076 KB Output is correct
21 Correct 13 ms 5088 KB Output is correct
22 Correct 11 ms 5092 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 3 ms 4052 KB Output is correct
25 Correct 15 ms 5076 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 12 ms 5076 KB Output is correct
28 Correct 2 ms 3284 KB Output is correct
29 Correct 20 ms 5332 KB Output is correct
30 Correct 17 ms 5204 KB Output is correct
31 Correct 17 ms 5236 KB Output is correct
32 Correct 15 ms 5092 KB Output is correct
33 Correct 14 ms 5076 KB Output is correct
34 Correct 15 ms 4704 KB Output is correct
35 Correct 16 ms 4820 KB Output is correct
36 Correct 12 ms 4740 KB Output is correct
37 Correct 9 ms 4704 KB Output is correct
38 Runtime error 103 ms 89176 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3152 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 10 ms 3284 KB Output is correct
6 Correct 8 ms 5076 KB Output is correct
7 Correct 9 ms 5076 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 3 ms 4052 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 13 ms 4692 KB Output is correct
13 Correct 106 ms 4612 KB Output is correct
14 Correct 174 ms 4860 KB Output is correct
15 Correct 156 ms 4716 KB Output is correct
16 Execution timed out 5112 ms 785092 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 55 ms 3980 KB Output is correct
5 Correct 111 ms 4684 KB Output is correct
6 Correct 11 ms 5176 KB Output is correct
7 Correct 13 ms 5076 KB Output is correct
8 Correct 20 ms 5336 KB Output is correct
9 Runtime error 107 ms 89188 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -