Submission #1312902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312902		Johan	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	263 ms	77256 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 4;
bool vis[N];
vector < int > adj[N];
vector < int > par;
vector < vector < int > > np;
int find(int u){
	if(par[u] < 0)
		return u;
	else return par[u] = find(par[u]);
}
void uni(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v)return;
	par[u] += par[v];
	par[v] = u;
}
void dfs(int s, int u, vector < vector < int > > &ans){
	np[s][u]++;
	vis[u] = true;
	for(auto v : adj[u]){
		if(!vis[v])dfs(s, v, ans);
	}
	vis[u] = false;
}
void create(vector < vector < int > > ans, int n){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(ans[i][j] > 0){
				adj[i].push_back(j);
//				adj[j].push_back(i);
			}
		}
	}
	for(int u = 0; u < n; u++){
		for(int v = 0; v < n; v++)
			vis[v] = false;
		dfs(u, u, ans);
	}
}
void reset_all(int n) {
  np.assign(n, vector<int>(n, 0));
	par.assign(n, -1);
	for(int i = 0; i < n; i++) {
		adj[i].clear();
		vis[i] = false;
	}
}
int construct(vector < vector < int > > p){
	int n = p.size();
	reset_all(n);
	set < int > lnn[n];
	vector < int > ln[n];
	map < int, map < int , int > > cnt;
	for(int i = 0; i < n; i++){
		vector < int > v1, v2;
		for(int j = 0; j < n; j++){
			if(p[i][j] >= 1 && i != j){
				uni(i, j);
				cnt[i][p[i][j]]++;
				if(p[i][j] == 1){
					ln[i].push_back(j);
					lnn[i].insert(j);
				}
			}	
		}
	}	
	set < int > v;
	vector < int > g[n];
	int q = 0;
	for(int i = 0; i < n; i++){
		v.insert(find(i));
		g[find(i)].push_back(i);
		q += ln[i].size() == 0;
	}
	vector < vector < int > > ans(n, vector < int > (n, 0));
	for(auto pre : v){
		vector < int > cycle;
		for(auto i : g[pre]){
			if(cnt[i][2] == g[pre].size() - 1)
				cycle.push_back(i);
		}
		for(int i = 0; i < (int)cycle.size() - 1; i++){
			int u = cycle[i];
			int v = cycle[i + 1];
			ans[u][v] = ans[v][u] = 1;
		}
//		for(auto i : cycle)cout << i << ' ';cout << endl;
		map < int , int > vis;
		int lst = ((int)cycle.size() == 0 ? -1 : cycle.back());
		int bgn = ((int)cycle.size() == 0 ? -1 : cycle.back());
		for(auto i : g[pre]){
			if(cnt[i][2] == g[pre].size() - 1 || vis[i])
				continue;
			vector < int > cur = {i};
			for(auto j : ln[i]){
				cur.push_back(j);
				vis[j] = 1;
			}
			if(bgn == -1)bgn = cur[0];
			if(lst != -1)ans[lst][cur[0]] = ans[cur[0]][lst] = 1;
			for(int j = 0; j < cur.size() - 1; j++){
				int u = cur[j];
				int v = cur[j + 1];
				ans[u][v] = ans[v][u] = 1;
			}
			lst = cur[0];
		}
		if((int)cycle.size() > 0 && lst != cycle[0])
			ans[lst][cycle[0]] = ans[cycle[0]][lst] = 1;
		else if((int)cycle.size() == 0 && bgn != -1 && lst != -1 && bgn != lst){
			ans[bgn][lst] = ans[lst][bgn] = 1;
		}
	} 
	if(q == n){
		create(ans, n);
		bool ok = true;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++)
				ok &= (p[i][j] == np[i][j]);
		}
		if(!ok)
			return 0;
		build(ans);
		return 1;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(find(i) != find(j))continue;
			if(lnn[i].count(j) || i == j )np[i][j] = 1;
			else np[i][j] = 2;
		}
	}
	bool ok = true;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			ok &= (p[i][j] == np[i][j]);
	}
	if(!ok)
		return 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			np[i][j] = 0;
	create(ans, n);
	ok = true;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			ok &= (p[i][j] == np[i][j]);
	}
	if(!ok)
		return 0;
	build(ans);
	return 1;
}
/*
7
1 1 1 2 2 2 2
1 1 1 2 2 2 2
1 1 1 2 2 2 2
2 2 2 1 2 1 2
2 2 2 2 1 2 1
2 2 2 1 2 1 2
2 2 2 2 1 2 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