Submission #960819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960819	2024-04-11T05:30:30 Z	Trisanu_Das	Jail (JOI22_jail)	C++17	49 / 100	5000 ms	1048580 KB

jail

#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	5 ms	10880 KB	Output is correct
2	Correct	2 ms	10844 KB	Output is correct
3	Correct	4 ms	6748 KB	Output is correct
4	Correct	106 ms	109784 KB	Output is correct
5	Correct	110 ms	110192 KB	Output is correct
6	Correct	21 ms	112476 KB	Output is correct
7	Correct	21 ms	110272 KB	Output is correct
8	Correct	29 ms	110552 KB	Output is correct
9	Runtime error	200 ms	292452 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	3 ms	10840 KB	Output is correct
2	Correct	2 ms	6748 KB	Output is correct
3	Correct	24 ms	116576 KB	Output is correct
4	Correct	20 ms	114524 KB	Output is correct
5	Correct	20 ms	116572 KB	Output is correct
6	Correct	23 ms	114528 KB	Output is correct
7	Correct	22 ms	114556 KB	Output is correct
8	Correct	21 ms	118620 KB	Output is correct
9	Correct	21 ms	116592 KB	Output is correct
10	Correct	22 ms	116568 KB	Output is correct
11	Correct	20 ms	116568 KB	Output is correct
12	Correct	16 ms	116368 KB	Output is correct
13	Correct	18 ms	114524 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	10840 KB	Output is correct
2	Correct	2 ms	6748 KB	Output is correct
3	Correct	24 ms	116576 KB	Output is correct
4	Correct	20 ms	114524 KB	Output is correct
5	Correct	20 ms	116572 KB	Output is correct
6	Correct	23 ms	114528 KB	Output is correct
7	Correct	22 ms	114556 KB	Output is correct
8	Correct	21 ms	118620 KB	Output is correct
9	Correct	21 ms	116592 KB	Output is correct
10	Correct	22 ms	116568 KB	Output is correct
11	Correct	20 ms	116568 KB	Output is correct
12	Correct	16 ms	116368 KB	Output is correct
13	Correct	18 ms	114524 KB	Output is correct
14	Correct	2 ms	10840 KB	Output is correct
15	Correct	2 ms	10844 KB	Output is correct
16	Correct	22 ms	116572 KB	Output is correct
17	Correct	21 ms	116584 KB	Output is correct
18	Correct	20 ms	114524 KB	Output is correct
19	Correct	3 ms	19036 KB	Output is correct
20	Correct	20 ms	114420 KB	Output is correct
21	Correct	20 ms	114524 KB	Output is correct
22	Correct	19 ms	114524 KB	Output is correct
23	Correct	2 ms	14940 KB	Output is correct
24	Correct	13 ms	113340 KB	Output is correct
25	Correct	22 ms	116504 KB	Output is correct
26	Correct	14 ms	116572 KB	Output is correct
27	Correct	20 ms	114532 KB	Output is correct
28	Correct	4 ms	25180 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	10840 KB	Output is correct
2	Correct	2 ms	6748 KB	Output is correct
3	Correct	24 ms	116576 KB	Output is correct
4	Correct	20 ms	114524 KB	Output is correct
5	Correct	20 ms	116572 KB	Output is correct
6	Correct	23 ms	114528 KB	Output is correct
7	Correct	22 ms	114556 KB	Output is correct
8	Correct	21 ms	118620 KB	Output is correct
9	Correct	21 ms	116592 KB	Output is correct
10	Correct	22 ms	116568 KB	Output is correct
11	Correct	20 ms	116568 KB	Output is correct
12	Correct	16 ms	116368 KB	Output is correct
13	Correct	18 ms	114524 KB	Output is correct
14	Correct	2 ms	10840 KB	Output is correct
15	Correct	2 ms	10844 KB	Output is correct
16	Correct	22 ms	116572 KB	Output is correct
17	Correct	21 ms	116584 KB	Output is correct
18	Correct	20 ms	114524 KB	Output is correct
19	Correct	3 ms	19036 KB	Output is correct
20	Correct	20 ms	114420 KB	Output is correct
21	Correct	20 ms	114524 KB	Output is correct
22	Correct	19 ms	114524 KB	Output is correct
23	Correct	2 ms	14940 KB	Output is correct
24	Correct	13 ms	113340 KB	Output is correct
25	Correct	22 ms	116504 KB	Output is correct
26	Correct	14 ms	116572 KB	Output is correct
27	Correct	20 ms	114532 KB	Output is correct
28	Correct	4 ms	25180 KB	Output is correct
29	Correct	29 ms	114580 KB	Output is correct
30	Correct	24 ms	116624 KB	Output is correct
31	Correct	23 ms	116568 KB	Output is correct
32	Correct	23 ms	116564 KB	Output is correct
33	Correct	21 ms	116572 KB	Output is correct
34	Correct	22 ms	114200 KB	Output is correct
35	Correct	23 ms	116568 KB	Output is correct
36	Correct	20 ms	116360 KB	Output is correct
37	Correct	18 ms	113952 KB	Output is correct

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	10840 KB	Output is correct
2	Correct	2 ms	6748 KB	Output is correct
3	Correct	24 ms	116576 KB	Output is correct
4	Correct	20 ms	114524 KB	Output is correct
5	Correct	20 ms	116572 KB	Output is correct
6	Correct	23 ms	114528 KB	Output is correct
7	Correct	22 ms	114556 KB	Output is correct
8	Correct	21 ms	118620 KB	Output is correct
9	Correct	21 ms	116592 KB	Output is correct
10	Correct	22 ms	116568 KB	Output is correct
11	Correct	20 ms	116568 KB	Output is correct
12	Correct	16 ms	116368 KB	Output is correct
13	Correct	18 ms	114524 KB	Output is correct
14	Correct	2 ms	10840 KB	Output is correct
15	Correct	2 ms	10844 KB	Output is correct
16	Correct	22 ms	116572 KB	Output is correct
17	Correct	21 ms	116584 KB	Output is correct
18	Correct	20 ms	114524 KB	Output is correct
19	Correct	3 ms	19036 KB	Output is correct
20	Correct	20 ms	114420 KB	Output is correct
21	Correct	20 ms	114524 KB	Output is correct
22	Correct	19 ms	114524 KB	Output is correct
23	Correct	2 ms	14940 KB	Output is correct
24	Correct	13 ms	113340 KB	Output is correct
25	Correct	22 ms	116504 KB	Output is correct
26	Correct	14 ms	116572 KB	Output is correct
27	Correct	20 ms	114532 KB	Output is correct
28	Correct	4 ms	25180 KB	Output is correct
29	Correct	29 ms	114580 KB	Output is correct
30	Correct	24 ms	116624 KB	Output is correct
31	Correct	23 ms	116568 KB	Output is correct
32	Correct	23 ms	116564 KB	Output is correct
33	Correct	21 ms	116572 KB	Output is correct
34	Correct	22 ms	114200 KB	Output is correct
35	Correct	23 ms	116568 KB	Output is correct
36	Correct	20 ms	116360 KB	Output is correct
37	Correct	18 ms	113952 KB	Output is correct
38	Runtime error	194 ms	300484 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	10840 KB	Output is correct
2	Correct	2 ms	10844 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	1 ms	6572 KB	Output is correct
5	Correct	11 ms	23132 KB	Output is correct
6	Correct	15 ms	112476 KB	Output is correct
7	Correct	16 ms	114524 KB	Output is correct
8	Correct	3 ms	19072 KB	Output is correct
9	Correct	2 ms	14980 KB	Output is correct
10	Correct	14 ms	115464 KB	Output is correct
11	Correct	4 ms	25180 KB	Output is correct
12	Correct	19 ms	114152 KB	Output is correct
13	Correct	90 ms	116132 KB	Output is correct
14	Correct	126 ms	116316 KB	Output is correct
15	Correct	112 ms	118100 KB	Output is correct
16	Execution timed out	6114 ms	1048580 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	10880 KB	Output is correct
2	Correct	2 ms	10844 KB	Output is correct
3	Correct	4 ms	6748 KB	Output is correct
4	Correct	106 ms	109784 KB	Output is correct
5	Correct	110 ms	110192 KB	Output is correct
6	Correct	21 ms	112476 KB	Output is correct
7	Correct	21 ms	110272 KB	Output is correct
8	Correct	29 ms	110552 KB	Output is correct
9	Runtime error	200 ms	292452 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

Submission #960819

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 28.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
16.0 / 16.0

Subtask #4
28.0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0