Submission #1232817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232817		M_W_13	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	132 ms	22336 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back

int construct(std::vector<std::vector<int>> p) {
	vector<vector<int>> b;
	int n = p.size();
	rep(i, n) {
		b.pb({});
		rep(j, n) {
			b[i].pb(0);
		}
	}
	int jaka[n];
	rep(i, n) {
		jaka[i] = -1;
	}
	rep(i, n) {
		rep(j, n) {
			if (p[i][j] == 3) return 0;
		}
	}
	vector<int> vec[n];
	rep(i, n) {
		if (jaka[i] == -1) {
			jaka[i] = i;
			int it = i + 1;
			it--;
			vec[it].pb(i);
			for (int j = i + 1; j < n; j++) {
				if (p[i][j] == 1) {
					jaka[j] = i;
					b[i][j] = 1;
					b[j][i] = 1;
					vec[it].pb(j);
				}
			}
			int sz = vec[it].size();
			rep(v, n) {
				rep(j, sz - 1) {
					if (p[vec[it][j]][v] != p[vec[it][j + 1]][v]) return 0;
				}
			}
		}
	}
	int jaka2[n];
	rep(i, n) {
		jaka2[i] = -1;
	}
	// cout << "BRUH" << endl;
	rep(i, n) {
		// cout << "i = " << i << " jaka = " << jaka[i] << " jaka2 = " << jaka2[i] << '\n';
		if ((jaka[i] == i) && (jaka2[i] == -1)) {
			// cout << "SKUL" << endl;
			set<int> S;
			S.insert(jaka[i]);
			// cout << "T" << endl;
			jaka2[i] = i;
			vector<int> p2;
			p2.pb(i);
			// cout << "FR" << endl;
			for (int j = i + 1; j < n; j++) {
				if (p[i][j] != 2) continue;
				if (S.find(jaka[j]) != S.end()) continue;
				S.insert(jaka[j]);
				p2.pb(j);
				jaka2[j] = i;
			}
			int sz = p2.size();
			if (sz == 2) return 0;
			if (sz == 1) continue;
			// cout << "REL" << endl;
			set<int> pomoc;
			rep(i, n) {
				pomoc.insert(i);
			}
			rep(j, sz) {
				for (auto w: vec[p2[j]]) {
					pomoc.erase(w);
					rep(k, sz) {
						if (k == j) continue;
						if (p[p2[k]][w] != 2) return 0;
					}
				}
				int a = p2[j];
				int c = p2[(j + 1) % sz];
				b[a][c] = 1;
				b[c][a] = 1;
			}
			for (auto w: pomoc) {
				rep(j, sz) {
					if (p[w][p2[j]] != 0) return 0;
				}
			}
		}
	}
	// cout << "XDDD" << endl;
	build(b);
	return 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