Submission #1196077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196077		dosts	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	130 ms	22252 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;


struct DSU {
	vi dad;
	DSU(int nn) {
		dad.resize(nn);
		iota(all(dad),0ll);
	}
	int find(int x) {
		if (x == dad[x]) return x;
		return dad[x] = find(dad[x]);
	}

	void unite(int x,int y) {
		dad[find(x)] = find(y);
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<vi> answer(n,vi(n,0));
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			if (p[i][j] == 3) return 0;
		}
	}
	DSU dsu(n);
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			if (p[i][j]) dsu.unite(i,j);
		}
	}
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			if ((dsu.find(i) == dsu.find(j)) != !!(p[i][j])) return 0;
		}
	}

	DSU dsu2(n);
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			if (p[i][j] == 1) dsu2.unite(i,j);
		}
	}
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			if (dsu2.find(i) == dsu2.find(j) && p[i][j] != 1) return 0;
		}
	}
	vi stuf[n];
	for (int i = 0;i<n;i++) stuf[dsu2.find(i)].push_back(i);
	for (int i = 0;i<n;i++) {
		if (stuf[i].empty()) continue;
		for (int j = 0;j<stuf[i].size()-1;j++) {
			answer[stuf[i][j]][stuf[i][j+1]] = answer[stuf[i][j+1]][stuf[i][j]] = 1;
			if (p[stuf[i][j]] != p[stuf[i][j+1]]) return 0;
		}
	}
	vi uc;
	for (int i = 0;i<n;i++) if (stuf[i].size()) uc.push_back(stuf[i][0]);
	sort(all(uc));
	DSU dsu3(n);
	for (int i = 0;i<uc.size();i++) {
		int a = uc[i];
		int have = 0;
		for (int j = 0;j<n;j++) {
			if (p[a][j] == 2) {
				have = 1;
			}
		}
		if (!have) continue;
		int found = -1;
		for (int j = i+1;j<uc.size();j++) {
			int b = uc[j];
			if (p[a][b] == 2) {
				found = b;
				break;
			}
		}
		if (found == -1) {
			for (int j = 0;j<i;j++) {
				int b = uc[j];
				if (p[a][b] == 2) {
					found = b;
					break;
				}
			}
			if (found == -1) return 0;
		}
		dsu3.unite(a,found);
		answer[a][found] = answer[found][a] = 1;
		found = -1;
		for (int j = i-1;j>=0;j--) {
			int b = uc[j];
			if (p[a][b] == 2) {
				found = b;
				break;
			}
		}
		if (found == -1) {
			for (int j = uc.size()-1;j > i;j++) {
				int b = uc[j];
				if (p[a][b] == 2) {
					found = b;
					break;
				}
			}
			if (found == -1) return 0;
		}
		dsu3.unite(a,found);
		answer[a][found] = answer[found][a] = 1;
	}
	for (int i = 0;i<uc.size();i++) {
		for (int j = 0;j<uc.size();j++) {
			if (i == j) continue;
			if ((p[uc[i]][uc[j]] == 2) != (!!(dsu3.find(uc[i]) == dsu3.find(uc[j])))) return 0;
		}
	}
	build(answer);
	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