Submission #366972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366972	2021-02-15T21:18:00 Z	MilosMilutinovic	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	271 ms	30316 KB

supertrees

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

Compilation message

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

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 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	257 ms	30316 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 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	257 ms	30316 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	10 ms	1388 KB	Output is correct
13	Correct	238 ms	26064 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	123 ms	19180 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	253 ms	26604 KB	Output is correct
22	Correct	238 ms	26092 KB	Output is correct
23	Correct	257 ms	28140 KB	Output is correct
24	Correct	249 ms	26092 KB	Output is correct
25	Correct	108 ms	16748 KB	Output is correct
26	Correct	104 ms	16236 KB	Output is correct
27	Correct	271 ms	29164 KB	Output is correct
28	Correct	239 ms	26220 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	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Incorrect	0 ms	364 KB	WA in grader: Invalid number of columns in b
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Memory	Grader output
1	Correct	364 KB	Output is correct
2	Incorrect	364 KB	WA in grader: Invalid number of columns in b
3	Halted	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 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	257 ms	30316 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	10 ms	1388 KB	Output is correct
13	Correct	238 ms	26064 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	123 ms	19180 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	253 ms	26604 KB	Output is correct
22	Correct	238 ms	26092 KB	Output is correct
23	Correct	257 ms	28140 KB	Output is correct
24	Correct	249 ms	26092 KB	Output is correct
25	Correct	108 ms	16748 KB	Output is correct
26	Correct	104 ms	16236 KB	Output is correct
27	Correct	271 ms	29164 KB	Output is correct
28	Correct	239 ms	26220 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	1 ms	364 KB	Output is correct
31	Correct	0 ms	364 KB	Output is correct
32	Incorrect	0 ms	364 KB	WA in grader: Invalid number of columns in b
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 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	257 ms	30316 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	10 ms	1388 KB	Output is correct
13	Correct	238 ms	26064 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	123 ms	19180 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	62 ms	6892 KB	Output is correct
21	Correct	253 ms	26604 KB	Output is correct
22	Correct	238 ms	26092 KB	Output is correct
23	Correct	257 ms	28140 KB	Output is correct
24	Correct	249 ms	26092 KB	Output is correct
25	Correct	108 ms	16748 KB	Output is correct
26	Correct	104 ms	16236 KB	Output is correct
27	Correct	271 ms	29164 KB	Output is correct
28	Correct	239 ms	26220 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	1 ms	364 KB	Output is correct
31	Correct	0 ms	364 KB	Output is correct
32	Incorrect	0 ms	364 KB	WA in grader: Invalid number of columns in b
33	Halted	0 ms	0 KB	-

Submission #366972

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