Submission #367121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367121	2021-02-16T10:21:32 Z	MilosMilutinovic	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	261 ms	30188 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define pb push_back
const int N=1050;
vector<int> E[N];
vector<vector<int>> p;
void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);}
vector<int> Euler;
bool was[N];
void DFS1(int u){
	was[u]=true,Euler.pb(u);
	for(int v:E[u])if(!was[v]&&p[u][v]==1)DFS1(v);
}
void DFS2(int u){
	was[u]=true,Euler.pb(u);
	for(int v:E[u])if(!was[v]&&p[u][v]==2)DFS2(v);
}
int construct(vector<vector<int>> P){
	p=P;int n=(int)P.size();
	for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(p[i][j]>0)AddEdge(i,j);
	bool one=false,two=false;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==1)one=true;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==2)two=true;
	vector<vector<int>> ans(n,vector<int>(n,0));
	if(!one&&!two){build(ans);return 1;}
	if(one&&!two){
		for(int i=0;i<n;i++){
			if(!was[i]){
				DFS1(i);
				if((int)Euler.size()==1){Euler.clear();continue;}
				for(int x:Euler)for(int y:Euler)if(x!=y&&p[x][y]==0)return 0;
				for(int i=1;i<(int)Euler.size();i++){
					int x=Euler[i],y=Euler[i-1];
					ans[x][y]=ans[y][x]=1;
				}
				Euler.clear();
			}
		}
		build(ans);
		return 1;
	}
	if(!one&&two){
		for(int i=0;i<n;i++){
			if(!was[i]){
				DFS2(i);
				if((int)Euler.size()==1){Euler.clear();continue;}
				if((int)Euler.size()==2)return 0;
				for(int x:Euler)for(int y:Euler)if(x!=y&&p[x][y]==0)return 0;
				for(int i=1;i<(int)Euler.size();i++){
					int x=Euler[i],y=Euler[i-1];
					ans[x][y]=ans[y][x]=1;
				}
				int x=Euler[0],y=Euler.back();
				ans[x][y]=ans[y][x]=1;
				Euler.clear();
			}
		}
		build(ans);
		return 1;
	}
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:25:44: warning: control reaches end of non-void function [-Wreturn-type]
   25 |  vector<vector<int>> ans(n,vector<int>(n,0));
      |                                            ^

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	11 ms	1644 KB	Output is correct
7	Correct	252 ms	30188 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	11 ms	1644 KB	Output is correct
7	Correct	252 ms	30188 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	14 ms	1536 KB	Output is correct
13	Correct	250 ms	26092 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	7 ms	1132 KB	Output is correct
17	Correct	114 ms	19180 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	248 ms	26604 KB	Output is correct
22	Correct	245 ms	26092 KB	Output is correct
23	Correct	257 ms	28396 KB	Output is correct
24	Correct	250 ms	26092 KB	Output is correct
25	Correct	104 ms	16748 KB	Output is correct
26	Correct	123 ms	16236 KB	Output is correct
27	Correct	257 ms	29292 KB	Output is correct
28	Correct	261 ms	26108 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Runtime error	1 ms	492 KB	Execution killed with signal 6
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Runtime error	1 ms	492 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	11 ms	1644 KB	Output is correct
7	Correct	252 ms	30188 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	14 ms	1536 KB	Output is correct
13	Correct	250 ms	26092 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	7 ms	1132 KB	Output is correct
17	Correct	114 ms	19180 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	248 ms	26604 KB	Output is correct
22	Correct	245 ms	26092 KB	Output is correct
23	Correct	257 ms	28396 KB	Output is correct
24	Correct	250 ms	26092 KB	Output is correct
25	Correct	104 ms	16748 KB	Output is correct
26	Correct	123 ms	16236 KB	Output is correct
27	Correct	257 ms	29292 KB	Output is correct
28	Correct	261 ms	26108 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	0 ms	364 KB	Output is correct
31	Correct	0 ms	364 KB	Output is correct
32	Runtime error	1 ms	492 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	11 ms	1644 KB	Output is correct
7	Correct	252 ms	30188 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	14 ms	1536 KB	Output is correct
13	Correct	250 ms	26092 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	7 ms	1132 KB	Output is correct
17	Correct	114 ms	19180 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	248 ms	26604 KB	Output is correct
22	Correct	245 ms	26092 KB	Output is correct
23	Correct	257 ms	28396 KB	Output is correct
24	Correct	250 ms	26092 KB	Output is correct
25	Correct	104 ms	16748 KB	Output is correct
26	Correct	123 ms	16236 KB	Output is correct
27	Correct	257 ms	29292 KB	Output is correct
28	Correct	261 ms	26108 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	0 ms	364 KB	Output is correct
31	Correct	0 ms	364 KB	Output is correct
32	Runtime error	1 ms	492 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Submission #367121

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0