Submission #302054

#	Time	Username	Problem	Language	Result	Execution time	Memory
302054		Dovran	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	512 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

#define N 1009
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define sz() size()
#define pb push_back
#define pp() pop_back()

using namespace std;

int n, sz[N], p[N];
vector<vector<int>>c;
int vis[N][N], vs[N];
vector<pair<int, pii>>a;
vector<pii>b;
vector<int>e;
int vl[N];

int ata(int x){
	if(p[x]==x)
		return x;
	return p[x]=ata(p[x]);
}

void uni(int x, int y){
	x=ata(x);
	y=ata(y);
	
	if(sz[y]>sz[x])
		swap(x, y);
	
	sz[x]+=sz[y];
	p[y]=x, sz[y]=0;
	c[x][y]=1, c[y][x]=1;
	return;
}

int construct(vector<vector<int>>v){
	int asd=0;
	n=v.sz();
	c.resize(n);
	for(int i=0; i<n; i++)
		sz[i]=1, p[i]=i, vl[i]=-1;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			c[i].pb(0);
			if(v[i][j]>0 and i!=j)
				a.pb({v[i][j], {i, j}}), v[j][i]=-1;
			if(v[i][j]==3)
				asd=1;
			if(v[i][j]==0)
				b.pb({i, j});
		}
	}
	for(auto i:a)
		if(ata(i.ss.ff)!=ata(i.ss.ss) and i.ff==1)
			uni(i.ss.ff, i.ss.ss);
	
	int dsa=0;
	for(auto i:a){
		if(i.ff==2){
			dsa++;
			int x=ata(i.ss.ff);
			int y=ata(i.ss.ss);
			if(x!=y and !vis[x][y] and !vis[y][x])
				vis[x][y]=vis[y][x]=1, c[x][y]=c[y][x]=1, vs[x]=vs[y]=1;
			else
				asd=1;
		}
	}
	for(auto i:b)
		if(ata(i.ff)==ata(i.ss))
			asd=1;
	if(asd or dsa==1)
		return 0;
	int qwe=-1;
	dsa=-1;
	for(int i=0; i<n; i++){
		if(vs[i]){
			if(dsa<0)
				dsa=i;
			qwe=i;
		}
	}
	c[dsa][qwe]=1;
	c[qwe][dsa]=1;
	build(c);
	return 1;
}
/*
int main(){
	int dsa, qwe;
	vector<vector<int>>v;
	cin>>dsa;
	v.resize(dsa);
	for(int i=0; i<dsa ;i++)
		for(int j=0; j<dsa; j++)
			cin>>qwe, v[i].pb(qwe);
	construct(v);
}
*/

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