oj.uz

Submission #756183

# Submission time Handle Problem Language Result Execution time Memory
756183 2023-06-11T09:22:18 Z Trumling Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 184 ms 26004 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -