Submission #300609

#	Time	Username	Problem	Language	Result	Execution time	Memory
300609		b00n0rp	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	291 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second

const int MX = 1005;

int n;
int par[MX];
int sz[MX];

int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
}

void merge(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x,y);
	par[y] = x;
	sz[x] += sz[y];
}

bitset<MX> vis;

int construct(vvi p) {
	n = p.size();
	vvi ans(n,vi(n,0));
	REP(i,n){
		par[i] = i;
		sz[i] = 1;
	}
	REP(i,n){
		REP(j,n){
			if(p[i][j] == 3) return 0;
			if(p[i][j]) merge(i,j);
		}
	}
	REP(i,n){
		REP(j,n){
			if(!p[i][j]){
				if(find(i) == find(j)) return 0;
			}
		}
	}
	REP(i,n) par[i] = find(i);
	REP(i,n){
		if(vis[i]) continue;
		vi cc;
		REP(j,n){
			if((!vis[j]) and par[i] == par[j]){
				vis[j] = 1;
				cc.pb(j);
			}
		}
		for(auto x:cc){
			vis[x] = 0;
			par[x] = x;
			sz[x] = 1;
		}
		vi corners;
		for(auto x:cc){
			for(auto y:cc){
				if(p[x][y] == 1){
					merge(x,y);
				}
			}
		}
		for(auto x:cc) par[x] = find(x);
		for(auto x:cc){
			if(vis[x]) continue;
			vi cc2;
			corners.pb(x);
			for(auto y:cc){
				if((!vis[y]) and par[x] == par[y]){
					vis[y] = 1;
					cc2.pb(y);
				}
			}
			REP(j,(int)cc2.size()-1){
				ans[cc2[j]][cc2[j+1]] = 1;
				ans[cc2[j+1]][cc2[j]] = 1;
			}
		}
		REP(j,(int)corners.size()-1){
			ans[corners[j]][corners[j+1]] = 1;
			ans[corners[j+1]][corners[j]] = 1;
		}
		if(corners.size() == 1) continue;
		if(corners.size() == 2) return 0;
		ans[corners[0]][corners.back()] = 1;
		ans[corners.back()][corners[0]] = 1;
	}
	build(ans);
	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