Submission #302704

#	Time	Username	Problem	Language	Result	Execution time	Memory
302704		arnold518	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	282 ms	30200 KiB

supertrees

#include "supertrees.h"
#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++) for(int j=1; j<=N; j++) if(A[i][j]==3) return 0;
 
	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]]==2 && 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]);
		}
		if(cyc.size()==2) return 0;
		if(cyc.size()==1) continue;
		for(int i=0; i+1<cyc.size(); i++) addEdge(cyc[i], cyc[i+1]);
		addEdge(cyc.back(), cyc[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:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   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:54:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   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:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]==2 && Find(VV[i])==Find(VV[j])) return 0;
      |                ~^~~~~~~~~~
supertrees.cpp:55:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0; i<VV.size(); i++) for(int j=i+1; j<VV.size(); j++) if(A[VV[i]][VV[j]]==2 && Find(VV[i])==Find(VV[j])) return 0;
      |                                                 ~^~~~~~~~~~
supertrees.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   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: 4 / 4