답안 #756183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756183	2023-06-11T09:22:18 Z	Trumling	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	184 ms	26004 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

vector<bool>vis(1000,0);
vector<bool>vis2(1000,0);

vector<vector<int>>g;
vector<vector<int>>ans;
ll nn;
bool dfs1(int start,int beg)
{
	vis[start]=1;
	//for(int i=0;i<nn;i++)
		//if(g[start][i]!=g[beg][i] && i!=start && i!=beg)
		//	return 0;

	for(int i=0;i<nn;i++)
		if(!vis[i] && g[start][i]==1)
		{
			ans[i][start]=1;
			ans[start][i]=1;
			return dfs1(i,beg);
		}
	if(start==beg)
	vis[start]=0;

	return 1;
}

bool dfs2(int start,int beg)
{
	vis[start]=1;

	//for(int i=0;i<nn;i++)
		//if(g[start][i]!=g[beg][i] && i!=start && i!=beg)
			//return 0;
		
		

	//ll count=0;
	//for(int i=0;i<nn;i++)
		//if(g[start][i]==2)
		//count++;
	
	//if(count==1)
	//return 0;

	for(int i=0;i<nn;i++)
		if(!vis[i] && g[start][i]==2)
		{
			ans[i][start]=1;
			ans[start][i]=1;

			return dfs2(i,beg);
		}
	ans[start][beg]=1;
	ans[beg][start]=1;
	return 1;
}

int construct(vector<vector<int>> pr) 
{
	nn=pr.size();
	g=pr;

	ans.assign(nn,vector<int>(nn,0));

	for(int i=0;i<nn;i++)
	{
		bool now=dfs1(i,i);
		if(!now)
		return 0;
	}

	for(int i=0;i<nn;i++)
	{
		bool now=dfs2(i,i);
		if(!now)
		return 0;
	}

	for(int i=0;i<nn;i++)
	ans[i][i]=0;

	build(ans);
	return 1;

}

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1356 KB	Output is correct
7	Correct	164 ms	26004 KB	Output is correct

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1356 KB	Output is correct
7	Correct	164 ms	26004 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1300 KB	Output is correct
13	Correct	179 ms	25988 KB	Output is correct
14	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	0 ms	212 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	43 ms	6688 KB	Output is correct
5	Correct	182 ms	25872 KB	Output is correct
6	Correct	169 ms	25972 KB	Output is correct
7	Correct	184 ms	26000 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	45 ms	6652 KB	Output is correct
10	Correct	163 ms	25932 KB	Output is correct
11	Correct	172 ms	25932 KB	Output is correct
12	Correct	174 ms	26000 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Incorrect	1 ms	212 KB	Too many ways to get from 0 to 4, should be 1 found no less than 2
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1356 KB	Output is correct
7	Correct	164 ms	26004 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1300 KB	Output is correct
13	Correct	179 ms	25988 KB	Output is correct
14	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1356 KB	Output is correct
7	Correct	164 ms	26004 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1300 KB	Output is correct
13	Correct	179 ms	25988 KB	Output is correct
14	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-