Submission #625057

#	Time	Username	Problem	Language	Result	Execution time	Memory
625057		cfalas	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	184 ms	24068 KiB

supertrees

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

typedef vector<int> vi;
#define FORi(i,a,b) for(int i=((int)a);i<((int)b);i++)
#define FOR(i,n) FORi(i,0,n)

int par[10000];
int fnd(int a){
	if(par[a]==a) return a;
	par[a] = fnd(par[a]);
	return par[a];
}

void onion(int a, int b){
	par[fnd(a)] = fnd(b);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	FOR(i,n) par[i] = i;
	vector<std::vector<int>> adj(n, vi(n, 0));
	FOR(i,n){
		FOR(j,n){
			if(p[i][j] && fnd(i)!=fnd(j)){
				onion(i, j);
				adj[i][j] = 1;
				adj[j][i] = 1;
			}
			else if(!p[i][j] && fnd(i)==fnd(j)){
				return 0;
			}
		}
	}
	build(adj);
	return 1;
}

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