oj.uz

답안 #1078814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078814 2024-08-28T06:32:20 Z Faisal_Saqib 슈퍼트리 잇기 (IOI20_supertrees) C++17
11 / 100
 142 ms 31316 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int reach[N][N],tree_case[N][N];
int par[N],par1[N];
void init(int n)
{
	for(int i=0;i<n;i++)
		par[i]=par1[i]=i;
}
int get(int x)
{
	if(par[x]==x)return x;
	return par[x]=get(par[x]);
}
int get1(int x)
{
	if(par1[x]==x)return x;
	return par1[x]=get1(par1[x]);
}
bool merge(int x,int y)
{
	x=get(x);
	y=get(y);
	if(x==y)return 0;
	par[y]=x;
	return 1;
}
bool merge1(int x,int y)
{
	x=get1(x);
	y=get1(y);
	if(x==y)return 0;
	par1[y]=x;
	return 1;
}
vector<int> ma[N];
int head;
void dfs(int x)
{
	reach[head][x]=1;
	for(auto y:ma[x])
		if(!reach[head][y])
			dfs(y);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	init(n);
	for(int i=0;i<n;i++)
	{
		if(p[i][i]!=1) // i i is always one
			return 0;
		for(int j=0;j<n;j++)
			tree_case[i][j]=reach[i][j]=0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(p[i][j]==1)
			{
				tree_case[i][j]=tree_case[j][i]=merge1(i,j);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(i==get(i))
		{
			vector<int> cur={i};
			for(int j=i+1;j<n;j++)
			{
				if(get(j)==j)
				{
					bool han=1;
					for(auto k:cur)
					{
						if(p[k][j]!=2)
						{
							han=0;
							break;
						}
					}
					if(han)
					{
						cur.push_back(j);
						merge(i,j);
					}
				}
			}
			if(cur.size()==1)continue;
			if(cur.size()==2)
				return 0;
			cur.push_back(i);
			for(int j=1;j<cur.size();j++)
			{
				int x=cur[j-1];
				int y=cur[j];
				tree_case[x][y]=tree_case[y][x]=1;
				merge(x,y);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{	
			if(tree_case[i][j])
			{
				ma[i].push_back(j);
				ma[j].push_back(i);
			}
		}
	}
	vector<vector<int>> answer(n,vector<int>(n,0));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			answer[i][j]=tree_case[i][j];
			reach[i][j]=0;
		}
		// head=i;
		// dfs(i);
		// for(int j=0;j<n;j++)
		// {
		// 	p[i][j]-=(p[i][j]==2);// make 2 to 1
		// 	if(reach[i][j]!=p[i][j])
		// 	{
		// 		return 0;
		// 	}
		// }
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j=1;j<cur.size();j++)
      |                ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 2928 KB Output is correct
7 Correct 126 ms 30036 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 2928 KB Output is correct
7 Correct 126 ms 30036 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 142 ms 31304 KB Output is correct
14 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 472 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 6 ms 2904 KB Output is correct
9 Correct 122 ms 31188 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 2908 KB Output is correct
13 Correct 136 ms 31144 KB Output is correct
14 Incorrect 0 ms 344 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 33 ms 10124 KB Output is correct
5 Correct 127 ms 31268 KB Output is correct
6 Correct 118 ms 31312 KB Output is correct
7 Correct 138 ms 31296 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 31 ms 10144 KB Output is correct
10 Correct 119 ms 31264 KB Output is correct
11 Correct 133 ms 31316 KB Output is correct
12 Correct 134 ms 31312 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 15 ms 6688 KB Answer gives possible 0 while actual possible 1
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 2928 KB Output is correct
7 Correct 126 ms 30036 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 142 ms 31304 KB Output is correct
14 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 2928 KB Output is correct
7 Correct 126 ms 30036 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 142 ms 31304 KB Output is correct
14 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -