제출 #1166187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166187		catch_me_if_you_can	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	127 ms	22288 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17

const int MX = 1e3+5;

int W[MX][MX];

int pa[2][MX];

int tp[2][MX];

/*void build(vector<vector<int>> sk)
{
	cout << "Check out this graph: " << endl;
	int n = sk.size(); cout << "size = " << n << endl;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			cout << sk[i][j] << " ";
		cout << endl;
	}
}*/

int leader(int u, int s)
{
	if(pa[s][u] < 0)
		return u;
	else
		return pa[s][u] = leader(pa[s][u], s);	
}

void merge(int u, int v, int Wr, int s)
{
	u = leader(u, s);
	v = leader(v, s);
	if(u == v)
	{
		tp[s][v] = max(tp[s][v], Wr);
		return;
	}
	if(pa[s][u] < pa[s][v])
		swap(u, v);
	pa[s][v]+=pa[s][u];
	pa[s][u] = v;
	tp[s][v] = max(tp[s][v], max(Wr, tp[s][u]));
	return;
}

int construct(vector<vector<int>> W)
{
	int n = W.size();
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			pa[j][i] = -1;
			tp[j][i] = 1;
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i == j)
				continue;
			if(W[i][j])
				merge(i, j, W[i][j], 0);
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i == j)
				continue;
			if(W[i][j] == 0)
				continue;
			if(W[i][j] == 1)
				merge(i, j, 0, 1);
		}
	}
	bool stuff = 1;
	vector<int> comp[2][n+1];
	for(int i = 0; i < n; i++)
	{
		for(int s = 0; s < 2; s++)
			comp[s][leader(i, s)].pb(i);
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if((i==j))
			{
				stuff = stuff&(W[i][j] == 1);
				//cout << "nval: " << stuff << endl;
				continue;
			}
			int expect = (leader(i, 0) == leader(j, 0))? ((leader(i, 1) == leader(j, 1))? 1 : tp[0][leader(i, 0)]) : 0;
			//cout << "For i = " << i << " and j = " << j << " we expect = " << expect << endl;
			stuff = stuff&(W[i][j] == expect);
			//cout << "nval: " << stuff << endl;
		}
	}
	vector<in> edges;
	for(int i = 0; i < n; i++)
	{
		if(leader(i, 0) != i)
			continue;
		set<int> sp;
		for(int x: comp[0][i])
			sp.insert(leader(x, 1));
		vector<int> dew;
		for(auto x: sp)
		{
			for(int T = 1; T < comp[1][x].size(); T++)
				edges.pb({comp[1][x][T-1], comp[1][x][T]});
			dew.pb(x);
		}
		int Ww = tp[0][i];
		if(Ww == 3)
		{
			stuff = 0;
			break;
		}
		else if(Ww == 2)
		{
			if(sp.size() < 3)
			{
				//cout << "size of level 2 comp is < 3" << endl;
				stuff = 0;
				break;
			}
			int N = dew.size();
			for(int i = 0; i < N; i++)
				edges.pb({dew[i], dew[(i+1)%N]});
		}
	}
	if(stuff == 0)
		return 0;
	vector<vector<int>> ans(n, vector<int> (n, 0));
	for(auto [u, v]: edges)
		ans[u][v] = ans[v][u] = 1;
	build(ans);
	return 1;
}

/*signed main()
{
	int n; cin >> n;
	vector<vector<int>> ways;
	ways.resize(n);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			int x; cin >> x;
			ways[i].pb(x);
		}
	}
	cout << construct(ways) << endl;
	return 0;
}*/

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