Submission #303018

#	Time	Username	Problem	Language	Result	Execution time	Memory
303018		alishahali1382	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	271 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=2010, LOG=20;

vector<int> vec[MAXN];
vector<vector<int>> answer;

struct DSU{
	int par[MAXN];
	DSU(){
		iota(par, par+MAXN, 0);
	}
	int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
	void join(int x, int y){ par[get(x)]=get(y);}
} dsu1, dsu2;

inline void addedge(int u, int v){
	answer[u][v]=answer[v][u]=1;
}

int construct(vector<vector<int>> A){
	int n=A.size();
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for (int i=0; i<n; i++) for (int j=0; j<n; j++){
		if (A[i][j]>=1) dsu1.join(i, j);
		if (A[i][j]==1) dsu2.join(i, j);
		if (A[i][j]==3) return 0;
	}
	for (int i=0; i<n; i++) if (dsu2.par[i]==i) vec[dsu1.get(i)].pb(i);
	
	for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (i!=j){
		if (A[i][j]==0 && dsu1.get(i)==dsu1.get(j)) return 0;
		if (A[i][j]>1 && dsu2.get(i)==dsu2.get(j)) return 0;
	}
	for (int i=0; i<n; i++) if (vec[i].size()>=2){
		if (vec[i].size()==2) return 0; // :(
		for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-1]);
		addedge(vec[i][0], vec[i].back());
	}
	for (int i=0; i<n; i++) vec[i].clear();
	for (int i=0; i<n; i++) vec[dsu2.get(i)].pb(i);
	for (int i=0; i<n; i++) if (vec[i].size()>=2){
		for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-1]);
	}
	
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-1]);
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j=1; j<vec[i].size(); j++) addedge(vec[i][j], vec[i][j-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