Submission #428630

#	Time	Username	Problem	Language	Result	Execution time	Memory
428630		alishahali1382	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	264 ms	28112 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1010, LOG=20;

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

int n, m, k, x, y, u, v, t, a, b, ans;
int A[MAXN][MAXN];
vector<vi> out;
vi vec1[MAXN], vec2[MAXN];

void add_edge(int u, int v){
	out[u][v]=out[v][u]=1;
}

int construct(vector<vi> _A){
	n=SZ(_A);
	for (int i=0; i<n; i++) for (int j=0; j<n; j++) A[i][j]=_A[i][j];
	for (int i=0; i<n; i++) for (int j=0; j<n; j++){
		if (A[i][j]==3) return 0;
		if (A[i][j]) dsu12.join(i, j);
		if (A[i][j]==1) dsu1.join(i, j);
	}
	for (int i=0; i<n; i++) for (int j=0; j<n; j++){
		if (!A[i][j] && dsu12.joined(i, j)) return 0;
		if (A[i][j]==2 && dsu1.joined(i, j)) return 0;
	}
	for (int i=0; i<n; i++){
		vec1[dsu1.getpar(i)].pb(i);
		if (dsu1.par[i]==i) vec2[dsu12.getpar(i)].pb(i);	
	}
	out.resize(n, vi(n, 0));
	for (int i=0; i<n; i++){
		// debugv(vec1[i])
		// debugv(vec2[i])
		// cerr<<"\n";
		for (int j=1; j<SZ(vec1[i]); j++) add_edge(vec1[i][j-1], vec1[i][j]);
		// debug("shit")
		if (SZ(vec2[i])==2) return 0;
		if (SZ(vec2[i])>2){
			for (int j=1; j<SZ(vec2[i]); j++) add_edge(vec2[i][j], vec2[i][j-1]);
			add_edge(vec2[i].back(), vec2[i][0]);
		}
	}
	build(out);
	return 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