Submission #302106

#	Time	Username	Problem	Language	Result	Execution time	Memory
302106		arnold518	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	266 ms	30328 KiB

supertrees

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

int N, A[MAXN+10][MAXN+10], ans[MAXN+10][MAXN+10];

int par[MAXN+10];
vector<int> V[MAXN+10];

int Find(int x)
{
	if(x==par[x]) return x;
	return par[x]=Find(par[x]);
}

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	par[x]=y;
}

void addEdge(int x, int y)
{
	if(x==y) return;
	ans[x][y]=ans[y][x]=1;
}

int construct(vector<vector<int>> _P)
{
	N=_P.size();
	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) A[i][j]=_P[i-1][j-1];

	for(int i=1; i<=N; i++) par[i]=i;

	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(A[i][j]!=0) Union(i, j);
	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(A[i][j]==0 && Find(i)==Find(j)) return 0;

	for(int i=1; i<=N; i++) V[Find(i)].push_back(i);

	for(int i=1; i<=N; i++)
	{
		if(V[i].empty()) continue;
		if(V[i].size()==2) return 0;
		for(int j=0; j+1<V[i].size(); j++) addEdge(V[i][j], V[i][j+1]);
		addEdge(V[i].back(), V[i][0]);
	}

	vector<vector<int>> ans2;
	ans2=vector<vector<int>>(N, vector<int>(N));
	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) ans2[i-1][j-1]=ans[i][j];
	build(ans2);
	return 1;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4