Submission #366958

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366958	2021-02-15T20:30:11 Z	MilosMilutinovic	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	284 ms	27884 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> comp;
void DFS(int u){
	was[u]=true,comp.push_back(u);
	for(int v:E[u])if(!was[v])DFS(v);
}
int construct(vector<vector<int>> 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);
	vector<vector<int>> ans(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
		if(!was[i]){
			DFS(i);
			for(int x:comp)for(int y:comp)if(x!=y&&p[x][y]==0)return 0;
			for(int i=1;i<(int)comp.size();i++){
				int x=comp[i],y=comp[i-1];
				ans[x][y]=ans[y][x]=1;
			}
			comp.clear();
		}
	}
	build(ans);
	return 1;
}

Subtask #1

11.0 / 11.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	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	15 ms	1516 KB	Output is correct
7	Correct	284 ms	27884 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	0 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	15 ms	1516 KB	Output is correct
7	Correct	284 ms	27884 KB	Output is correct
8	Correct	1 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	11 ms	1260 KB	Output is correct
13	Correct	273 ms	23696 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	6 ms	1004 KB	Output is correct
17	Correct	124 ms	16748 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	73 ms	6456 KB	Output is correct
21	Correct	258 ms	24300 KB	Output is correct
22	Correct	257 ms	23788 KB	Output is correct
23	Correct	268 ms	25836 KB	Output is correct
24	Correct	259 ms	23788 KB	Output is correct
25	Correct	113 ms	14316 KB	Output is correct
26	Correct	115 ms	13804 KB	Output is correct
27	Correct	274 ms	26860 KB	Output is correct
28	Correct	264 ms	23788 KB	Output is correct

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	Incorrect	0 ms	364 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	492 KB	Too few ways to get from 0 to 1, should be 2 found 1
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	0 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	15 ms	1516 KB	Output is correct
7	Correct	284 ms	27884 KB	Output is correct
8	Correct	1 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	11 ms	1260 KB	Output is correct
13	Correct	273 ms	23696 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	6 ms	1004 KB	Output is correct
17	Correct	124 ms	16748 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	73 ms	6456 KB	Output is correct
21	Correct	258 ms	24300 KB	Output is correct
22	Correct	257 ms	23788 KB	Output is correct
23	Correct	268 ms	25836 KB	Output is correct
24	Correct	259 ms	23788 KB	Output is correct
25	Correct	113 ms	14316 KB	Output is correct
26	Correct	115 ms	13804 KB	Output is correct
27	Correct	274 ms	26860 KB	Output is correct
28	Correct	264 ms	23788 KB	Output is correct
29	Correct	0 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	Incorrect	0 ms	364 KB	Answer gives possible 1 while actual possible 0
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	0 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	15 ms	1516 KB	Output is correct
7	Correct	284 ms	27884 KB	Output is correct
8	Correct	1 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	11 ms	1260 KB	Output is correct
13	Correct	273 ms	23696 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	6 ms	1004 KB	Output is correct
17	Correct	124 ms	16748 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	73 ms	6456 KB	Output is correct
21	Correct	258 ms	24300 KB	Output is correct
22	Correct	257 ms	23788 KB	Output is correct
23	Correct	268 ms	25836 KB	Output is correct
24	Correct	259 ms	23788 KB	Output is correct
25	Correct	113 ms	14316 KB	Output is correct
26	Correct	115 ms	13804 KB	Output is correct
27	Correct	274 ms	26860 KB	Output is correct
28	Correct	264 ms	23788 KB	Output is correct
29	Correct	0 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	Incorrect	0 ms	364 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-