Submission #305806

#	Time	Username	Problem	Language	Result	Execution time	Memory
305806		tincan	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	260 ms	22264 KiB

supertrees

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<deque>
#include<string>
#include<unordered_map>
#include<bitset>
#include<random>
#include<chrono>
//Eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
using namespace std;
const int MAXN = 1005;
struct dsu {
	int arr[MAXN];
	dsu() { for (int i = 1; i < MAXN; i++) arr[i] = i; }
	int find(int s) { return arr[s] == s ? s : arr[s] = find(arr[s]); }
	void join(int a, int b) { if (find(a) != find(b)) arr[find(a)] = find(b); }
} st, st2;
vector<int> thng[MAXN];
void build(vector<vector<int>> b);
void make(int i, int i2, vector<vector<int>> &ans) {
	ans[i][i2] = ans[i2][i] = 1;
}
int construct(vector<vector<int>> p) {
	int N = p.size();
	for (int i = 0; i < N; i++) for (int i2 = 0; i2 < N; i2++) if (p[i][i2] == 3) return 0;
	vector<vector<int>> ans;
	for (int i = 0; i < N; i++) {
		ans.push_back(vector<int>(N));
		for (int i2 = 0; i2 < N; i2++) ans[i][i2] = 0;
	}
	for (int i = 0; i < N; i++) {
		for (int i2 = i + 1; i2 < N; i2++) {
			if (p[i][i2]) {
				if(p[i][i2] == 1) st2.join(i, i2);
				st.join(i, i2);
			}
		}
	}
	for (int i = 0; i < N; i++)
		for (int i2 = i + 1; i2 < N; i2++)
			if (!p[i][i2] && (st.find(i) == st.find(i2))) return 0;
	for (int i = 0; i < N; i++) {
		if (thng[st2.find(i)].size()) make(thng[st2.find(i)].back(), i, ans);
		thng[st2.find(i)].push_back(i);
	}
	for (int i = 0; i < N; i++) {
		for (int i2 = i + 1; i2 < N; i2++) {
			if (p[i][i2] == 2) {
				if (ans[st.find(i)][st.find(i2)]) return 0;
				make(st2.find(i), st2.find(i2), ans);
			}
		}
	}
	build(ans); 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