Submission #1273859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273859		crispxx	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	103 ms	22196 KiB

supertrees

#include "supertrees.h"

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

// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

struct dsu {
	vector<int> p, sz;
	
	dsu(int n) : p(n), sz(n) {
		iota(all(p), 0);
	}
	
	int find(int v) {
		return v == p[v] ? v : p[v] = find(p[v]);
	}
	
	void unite(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);
		p[v] = u;
		sz[u] += sz[v];
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	
	dsu d(n);
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 1) {
				d.unite(i, j);
			}
		}
	}
	
	vector<vector<int>> v(n);
	vector<vector<int>> b(n, vector<int>(n));
	
	for(int i = 0; i < n; i++) {
		v[d.find(i)].pb(i);
	}
	
	for(int i = 0; i < n; i++) {
		auto &u = v[i];
		
		for(int j = 0; j < (int)u.size(); j++) {
			for(int k = 0; k < (int)u.size(); k++) {
				if( u[j] == u[k] ) continue;
				if( p[ u[j] ][ u[k] ] != 1 ) return false;
			}
		}
		
		for(int j = 0; j + 1 < (int)u.size(); j++) {
			b[ u[j] ][ u[j + 1] ] = 1;
			b[ u[j + 1] ][ u[j] ] = 1;
		}
		
		u.clear();
	}
	
	dsu d2(n);
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 2) {
				d2.unite( d.find(i), d.find(j) );
			}
		}
	}
	
	for(int i = 0; i < n; i++) {
		v[d2.find(i)].pb(i);
	}
	
	for(int i = 0; i < n; i++) {
		auto &u = v[i];
		
		if(u.size() <= 1) {
			u.clear();
			continue;
		}
		
		if(u.size() < 3) return false;
		
		for(int j = 0; j < (int)u.size(); j++) {
			for(int k = 0; k < (int)u.size(); k++) {
				if( u[j] == u[k] ) continue;
				if( p[ u[j] ][ u[k] ] != 2 ) return false;
			}
		}
		
		for(int j = 0; j < (int)u.size(); j++) {
			int l = (j + 1 == (int)u.size() ? 0 : j + 1);
			b[ u[j] ][ u[l] ] = 1;
			b[ u[l] ][ u[j] ] = 1;
		}
		
		u.clear();
	}
	
	// dsu d3(n);
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 3) {
				// d3.unite( d.find(i), d.find(j) );
				return false;
			}
		}
	}
	
	/**
	for(int i = 0; i < n; i++) {
		v[d3.find(i)].pb(i);
	}
	
	for(int i = 0; i < n; i++) {
		auto &u = v[i];
		
		// cout << u.size() << endl;
		
		if(u.size() <= 1) continue;
		
		if(u.size() < 4) return false;
		
		for(int j = 0; j < (int)u.size(); j++) {
			for(int k = 0; k < (int)u.size(); k++) {
				if( u[j] == u[k] ) continue;
				if( p[ u[j] ][ u[k] ] != 3 ) return false;
			}
		}
		
		int u1 = u.back();
		
		u.pop_back();
		
		for(int j = 0; j < (int)u.size(); j++) {
			int l = (j + 1 == (int)u.size() ? 0 : j + 1);
			b[ u[j] ][ u[l] ] = 1;
			b[ u[l] ][ u[j] ] = 1;
			if(j == 0) {
				b[ u1 ][ u[j] ] = 1;
				b[ u[j] ][ u1 ] = 1;
				b[ u1 ][ u[l] ] = 1;
				b[ u[l] ][ u1 ] = 1;
			}
		}
	}
	**/
	
	build(b);
	
	return true;
}

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