Submission #301903

#	Time	Username	Problem	Language	Result	Execution time	Memory
301903		Dovran	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	268 ms	30160 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];
vector<pii>a;
vector<pii>b;
int vl[N];
/*
void build(vector<vector<int>>m){
	for(int i=0; i<m.sz(); i++){
		for(int j=0; j<m[i].sz(); j++)
			cout<<m[i][j]<<' ';
		cout<<'\n';
	}
}
*/
int ata(int x){
	if(p[x]==x)
		return x;
	return p[x]=ata(p[x]);
}

void dsu(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;
	
	return;
}

int construct(vector<vector<int>>v){
	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]==2)
				a.pb({i, j}), v[j][i]=3;
			if(v[i][j]==0)
				b.pb({i, j});
		}
	}
	for(auto i:a)
		if(ata(i.ff)!=ata(i.ss))
			dsu(i.ff, i.ss);
	int asd=0;
	for(auto i:a)
		if(ata(i.ff)!=ata(i.ss))
			dsu(i.ff, i.ss);
	for(auto i:b)
		if(ata(i.ff)==ata(i.ss))
			asd=1;
	for(auto i:a)
		if(sz[ata(i.ff)]<3)
			asd=1;
	if(asd)
		return 0;
	
	for(int i=0; i<n; i++){
		if(sz[ata(i)]>1){
			if(vl[p[i]]>=0)
				c[vl[p[i]]][i]=c[i][vl[p[i]]]=1;
			vl[p[i]]=i;
		}
	}
	for(int i=0; i<n; i++)
		if(vl[p[i]]>=0)
			c[vl[p[i]]][i]=c[i][vl[p[i]]]=1, vl[p[i]]=-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: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4