Submission #779383

#	Time	Username	Problem	Language	Result	Execution time	Memory
779383		andrej246	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	157 ms	22216 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,N) for(long long i = 0; (i) < (N); (i)++)
#define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++)
#define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc))

#define NL '\n'
#define EL cout << NL

#define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}

typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VLL;
typedef pair<ll,ll> PL;
typedef vector<PL> VPL;
typedef vector<VPL> VVPL;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	vector<bool> visited(n,0);
	FOR(s,n) {
		if (!visited[s]) {
			vector<int> branch;
			vector<int> cycle;
			vector<int> comp;
			vector<bool> incycle(n,false);
			vector<int> adress(n,-1);
			stack<pair<int,int>> st;
			int bnum = 0;
			st.push({s,0});
			while(!st.empty()) {
				int u = st.top().first;
				int t = st.top().second;
				st.pop();
				if (visited[u]) continue;
				//cout << u << " " << t << NL;
				visited[u] = true;
				bool is_cycle = true;
				FOR(v,n) {
					if (v == u) continue;
					if (p[u][v] >= 1) {
                        is_cycle = is_cycle && (p[u][v] == 2);
						int type = 0;
						if (p[u][v] == 1) {
                            if (adress[v] > 0 && adress[v] < t) type = t = adress[v];
                            if (t > 0) type = t;
							else if (adress[v] > 0) type = t = adress[v];
							else t = type = ++bnum;
						}
						st.push({v,type});
					}
				}
				if (is_cycle)  {
					cycle.push_back(u);
					incycle[u] = true;
				}
				else branch.push_back(u);
				adress[u] = t;
				comp.push_back(u);
			}
			//PRINTV(branch);
			//PRINTV(cycle);
			//PRINTV(adress);
			//PRINTV(incycle);
			for (auto u: comp) {
				for (auto v: comp) {
					int expected = 2;
					if (u == v) expected = 1;
					if ((adress[u] == adress[v]) && (adress[u] != 0)) expected = 1;
					if (expected != p[u][v]) return 0;
				}
			}
			for (auto u: branch) {
				FOR(v,n) {
					if (p[u][v] == 2 && !incycle[v]) {
                        return 0;
					}
				}
			}
			int prev_u = -1;
			for(auto u: branch) {
				if (prev_u >= 0) {
                    answer[u][prev_u] = answer[prev_u][u] = 1;
				}
				prev_u = u;
			}
			int prev_v = prev_u;
			int first_c  = prev_u;
			for (auto v: cycle) {
				if (prev_v >= 0) answer[v][prev_v] = answer[prev_v][v] = 1;
				prev_v = v;
				if (first_c == -1) first_c = v;
			}
			if (prev_v != first_c) answer[first_c][prev_v] = answer[prev_v][first_c] = 1;
		}
	}
	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