Submission #302101

#	Time	Username	Problem	Language	Result	Execution time	Memory
302101		arnold518	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	279 ms	30196 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)
{
	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++)
	{
		for(int j=0; j+1<V[i].size(); j++) addEdge(V[i][j], V[i][j+1]);
	}

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

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