Submission #603730

#	Time	Username	Problem	Language	Result	Execution time	Memory
603730		HamletPetrosyan	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	230 ms	22212 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>
using namespace std;

#define add push_back
#define len(a) ((int)(a).size())

int construct(vector<vector<int>> p) {
	vector<vector<int>> answer(len(p));
	vector<int> h(len(p)), s(len(p));
	vector<int> v[1005];

	int now = 0;
	for(int i = 0; i < len(p); i++){
		answer[i].resize(len(p));
		for(int j = 0; j < i; j++){
			if(p[i][j] != 0){
				h[i] = h[j];
				break;
			}
		}
		if(h[i] == 0){
			h[i] = ++now;
		}
		v[h[i]].add(i);
	}

	for(int i = 0; i < len(p); i++){
		for(int j = 0; j < len(p); j++){
			if(p[i][j] == 3) return 0;
			if(i == j) continue;
			if(p[i][j] != 0 && h[i] != h[j]){
//				cout << "E1.1" << endl;
				return 0;
			}
			if(p[i][j] == 0 && h[i] == h[j]){
//				cout << "E1.2" << endl;
				return 0;
			}
		}
	}

//	for(int i = 1; i <= now; i++){
//		for(int j = 0; j < len(v[i]); j++){
//			cout << v[i][j] << " ";
//		}
//		cout << endl;
//	}

	vector<vector<int>> a;
	int x, v1, v2;
	a.resize(1005);
	for(int i = 1; i <= now; i++){
		x = 0;
		for(int j = 0; j < len(v[i]); j++){
			v1 = v[i][j];
			for(int k = 0; k < j; k++){
				v2 = v[i][k];
				if(p[v1][v2] == 1){
					s[v1] = s[v2];
					break;
				}
			}
			if(s[v1] == 0){
				s[v1] = ++x;
			}
			a[s[v1]].add(v1);
		}

		if(x == 2) return 0;

		for(int j = 0; j < len(v[i]); j++){
			v1 = v[i][j];
			for(int k = 0; k < len(v[i]); k++){
				if(j == k) continue;
				v2 = v[i][k];
				if(p[v1][v2] != 1 && s[v1] == s[v2]){
//					cout << "E2.1" << endl;
					return 0;
				}
				if(p[v1][v2] == 1 && s[v1] != s[v2]){
//					cout << "E2.2" << endl << "----------" << endl << v1 << " " << v2 << " : " << s[v1] << " " << s[v2] << endl;
					return 0;
				}
			}
		}

		for(int j = 1; j <= x; j++){
			for(int k = 1; k < len(a[j]); k++){
				answer[a[j][k - 1]][a[j][k]] = answer[a[j][k]][a[j][k - 1]] = 1;
			}
			if(x > 1){
				if(j == 1) answer[a[j][0]][a[x][0]] = answer[a[x][0]][a[j][0]] = 1;
				else answer[a[j][0]][a[j - 1][0]] = answer[a[j - 1][0]][a[j][0]] = 1;
			}
		}
		for(int j = 1; j <= x; j++) a[j].clear();
	}

	build(answer);
	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