Submission #300278

#	Time	Username	Problem	Language	Result	Execution time	Memory
300278		easrui	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	283 ms	22520 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;

const int MN = 1e3+5;
const int MOD = 1e9+7;
const int INF = 1e9;

int par[MN];
vector<int> G[MN],L[MN],C;

int fnd(int u)
{
	return u==par[u] ? u : par[u]=fnd(par[u]);
}

void join(int u, int v)
{
	u = fnd(u), v = fnd(v);
	par[u] = v;
}

int construct(vector<vector<int>> p) {
    int n = p.size();
	for(int i=0; i<n; i++) par[i] = i;

	vector<vector<int>> ans;
	vector<int> v(n);
	for(int i=0; i<n; i++) ans.push_back(v);

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(p[i][j]) join(i,j);

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(fnd(i)==fnd(j)&&!p[i][j]) return 0;

	for(int i=0; i<n; i++) G[par[i]].push_back(i);

	for(int i=0; i<n; i++) par[i] = i;

	for(int t=0; t<n; t++){
		//FOR G[i]
		for(int i=0; i<n; i++) L[i].clear();
		C.clear();

		int nn = G[t].size();
		for(int i:G[t])
			for(int j:G[t])
				if(p[i][j]==1) join(i,j);

		for(int i:G[t])
			for(int j:G[t])
				if(fnd(i)==fnd(j)&&p[i][j]==2) return 0;

		for(int i:G[t]) if(par[i]==i){
			L[i].push_back(i);
			C.push_back(i);
		}
		for(int i:G[t]) if(par[i]!=i) L[par[i]].push_back(i);

		for(int i:G[t]){
			if(par[i]!=i) continue;
			for(int j=0; j<L[i].size()-1; j++){
				ans[L[i][j]][L[i][j+1]] = 1;
				ans[L[i][j+1]][L[i][j]] = 1;
			}
		}
		int c = C.size();
		if(c==2) return 0;

		for(int i=0; i<c; i++){
			ans[C[i]][C[(i+1)%c]] = 1;
			ans[C[(i+1)%c]][C[i]] = 1;
		}
	}
	
	for(int i=0; i<n; i++) ans[i][i] = 0;

	/*for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}*/
	build(ans);
	return 1;
}

/*int main()
{
	#ifdef L0TUS
    freopen("C:\\Users\\SKYPC364\\Documents\\Coding\\BOJ\\input.txt", "r", stdin);
    freopen("C:\\Users\\SKYPC364\\Documents\\Coding\\BOJ\\output.txt", "w", stdout);
	#endif
	int n;
	cin >> n;
	vector<vector<int>> p(n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++){
			int x;
			cin >> x;
			p[i].push_back(x);
		}
	construct(p);
}*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for(int j=0; j<L[i].size()-1; j++){
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:56:7: warning: unused variable 'nn' [-Wunused-variable]
   56 |   int nn = G[t].size();
      |       ^~

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