Submission #679768

#	Time	Username	Problem	Language	Result	Execution time	Memory
679768		mansur	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	231 ms	24052 KiB

supertrees

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

#define rall(s) s.end(), s.begin()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define pb push_back
#define vt vector
#define s second
#define f first
#define nl '\n'

using ll = long long;
//using pii = pair<int, int>;
//using pll = pair<ll, ll>;

using namespace std;

const int N = 1e5;

int pr[N], l[N];

int get(int x) {	
	if (pr[x] == x) return x;
	return pr[x] = get(pr[x]);
}

void unite(int a, int b) {
	a = get(a);
	b = get(b);
	if (a == b) return;
	if (l[a] > l[b]) swap(a, b);
	pr[a] = b;
	l[b] += l[a];
}

int construct(vt<vt<int>> p) {
	int n = sz(p);
	bool ok = 0;
	vt<vt<int>> b;
	for (int i = 0; i < n; i++) {
		pr[i] = i, l[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		vt<int> s;
		s.resize(n);
		b.pb(s);
	    for (int j = i + 1; j < n; j++) {
	    	if (p[i][j]) {
				unite(i, j);					    		
	    	}
	    	if (p[i][j] == 2) ok = 1;
	    }
	}        
	vt<int> was(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (!p[i][j] && get(i) == get(j)) return 0;
		}
    	if (was[i]) continue;
    	int x = get(i);
    	int lst = i;
    	was[i] = 1;
    	for (int j = i + 1; j < n; j++) {
			if (get(j) == x) {
				was[j] = 1;
				b[lst][j] = b[j][lst] = 1;	
				lst = j;
			}
    	}
    	if (ok && lst != i) {
    		if (b[i][lst] == 1) return 0;
    		b[lst][i] = b[i][lst] = 1;
    	}
    }
	build(b);
	return 1;
}

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