Submission #302339

#	Time	Username	Problem	Language	Result	Execution time	Memory
302339		arnold518	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	268 ms	30320 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++) par[i]=i;

	for(int p=1; p<=N; p++)
	{
		if(V[p].empty()) continue;
		vector<int> &VV=V[p];

		for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]==1) Union(VV[i], VV[j]);
		for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]!=1 && Find(VV[i])==Find(VV[j])) return 0;
		vector<int> cyc;
		for(auto it : VV)
		{
			if(par[it]==it) cyc.push_back(it);
			else addEdge(it, par[it]);
		}

		bool f1=false, f2=false;
		for(int i=0; i<cyc.size(); i++) for(int j=i+1; j<cyc.size(); j++)
		{
			if(A[cyc[i]][cyc[j]]==2) f1=true;
			if(A[cyc[i]][cyc[j]]==3) f2=true;
		}

		if(f1 && f2) return 0;
		if(!f1 && !f2) continue;

		if(cyc.size()==2) return 0;
		for(int i=0; i+1<cyc.size(); i++) addEdge(cyc[i], cyc[i+1]);
		addEdge(cyc.back(), cyc[0]);

		if(f2)
		{
			if(cyc.size()==3) return 0;
			addEdge(cyc[0], cyc[2]);
		}
	}

	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:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]==1) Union(VV[i], VV[j]);
      |                ~^~~~~~~~~~
supertrees.cpp:52:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]==1) Union(VV[i], VV[j]);
      |                                                 ~^~~~~~~~~~
supertrees.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]!=1 && Find(VV[i])==Find(VV[j])) return 0;
      |                ~^~~~~~~~~~
supertrees.cpp:53:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]!=1 && Find(VV[i])==Find(VV[j])) return 0;
      |                                                 ~^~~~~~~~~~
supertrees.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i=0; i<cyc.size(); i++) for(int j=i+1; j<cyc.size(); j++)
      |                ~^~~~~~~~~~~
supertrees.cpp:62:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i=0; i<cyc.size(); i++) for(int j=i+1; j<cyc.size(); j++)
      |                                                  ~^~~~~~~~~~~
supertrees.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0; i+1<cyc.size(); i++) addEdge(cyc[i], cyc[i+1]);
      |                ~~~^~~~~~~~~~~

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