Submission #561634

#	Time	Username	Problem	Language	Result	Execution time	Memory
561634		sentheta	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	256 ms	28232 KiB

supertrees

#include "supertrees.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second

#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define dbg(x) cout<<"?"<< #x <<" : "<<(x)<<endl; cout.flush();
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define all(x) (x).begin(), (x).end()


const int N = 1005;

struct Dsu{
	int p[N];
	V<int> v[N];
	void reset(){
		rep(i,0,N){
			p[i] = -1;
			v[i] = {i};
		}
	}
	int find(int x){
		if(p[x]==-1) return x;
		return p[x] = find(p[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		if((x=find(x))==(y=find(y))) return;
		// wlog sz(x) > sz(y)
		if(v[x].size() < v[y].size()) swap(x,y);
		
		p[y] = x;
		for(int i : v[y]) v[x].pb(i);
		v[y].clear();
	}
} dsu, t;

int n;
V<V<int>> ans, p;
void make_edge(int x,int y){
	ans[x][y] = ans[y][x] = 1;
}

bool f(V<int>& v){
	int sz = v.size();

	bool two = false, tri = false;
	for(int x : v) for(int y : v){
		two |= p[x][y]==2;
		tri |= p[x][y]==3;
	}
	if(two && tri) return false;

	// straight path
	if(!two && !tri){
		rep(i,1,sz){
			make_edge(v[i], v[i-1]);
		}
		return true;
	}
	
	// cycle grouping
	for(int x : v) for(int y : v){
		if(p[x][y] == 1){
			t.unite(x,y);
		}
	}
	
	// find main cycle
	V<int> lead;
	for(int x : v) if(t.find(x)==x){
		lead.pb(x);
	}
	if(lead.size() <= 2) return false;
	if(tri) return false;
	//if(tri && lead.size()<=3) return false;


	// make main cycle
	rep(i,0,lead.size()){
		make_edge(lead[i], lead[(i+1)%lead.size()]);
	}
	if(tri){
		make_edge(lead[0], lead[2]);
	}

	// group of each nodes
	for(int x : lead){
		for(int y : t.v[x]) if(y != x){
			make_edge(x, y);
		}
	}

	return true;
}

int construct(V<V<int>> _p) {
	p = _p; n = p.size();
	dsu.reset(); t.reset();
	ans = V<V<int>>(n,V<int>(n));

	// connected components
	rep(i,0,n) rep(j,0,i) if(p[i][j]){
		dsu.unite(i,j);
	}
	rep(i,0,n) rep(j,0,i) if(dsu.same(i,j)){
		if(p[i][j] == 0) return 0;
	}

	// solve per cc
	rep(i,0,n) if(dsu.find(i) == i){
		if(!f(dsu.v[i])) return 0;
	}

	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