Submission #625083

#	Time	Username	Problem	Language	Result	Execution time	Memory
625083		cfalas	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	212 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)
#define FOA(v,a) for(auto v : a)

int par[10000];
int lef[10000];
vector<vi> adj;

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);
}

vi vis;
void dfs(int x){
	vis[x] = true;
	FOA(v, adj[x]) if(!vis[v]) dfs(v);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	FOR(i,n) par[i] = i;
	adj.assign(n, vi(n, 0));
	int deg[n] = {};
	FOR(i,n){
		bool none = true;
		FOR(j,n){
			if(i==j) continue;
			if(p[i][j]==2 && fnd(i)!=fnd(j) && none){
				onion(i, j);
				adj[i][j] = 1;
				adj[j][i] = 1;
				deg[i]++;
				deg[j]++;
				none = false;
			}
			else if(p[i][j]==0 && fnd(i)==fnd(j)){
				return 0;
			}
		}
	}
	FOR(i,n){
		if(deg[i]==1){
			FOR(j,n) if(fnd(i)==fnd(j) && deg[j]==1 && i!=j){
				deg[i]++;
				deg[j]++;
				adj[i][j] = 1;
				adj[j][i] = 1;
			}
		}
	}
	FOR(i,n){
		vis.assign(n, 0);
		dfs(i);
		FOR(j,n) if(vis[i] && !p[i][j]) return 0;
	}
	build(adj);
	return 1;
}

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