Submission #798940

#	Time	Username	Problem	Language	Result	Execution time	Memory
798940		QwertyPi	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	182 ms	24232 KiB

supertrees

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

using namespace std;

struct DSU{
	int dsu[1001];
	void init(int n){
		for(int i = 0; i < n; i++){
			dsu[i] = i;
		}
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	void g(int x, int y){
		x = f(x), y = f(y);
		dsu[x] = y;
	}
} dsu0, dsu1;
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	dsu0.init(n), dsu1.init(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 3) return false;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] >= 1) dsu0.g(i, j);
			if(p[i][j] == 1) dsu1.g(i, j);
		}
	}
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 0 && dsu0.f(i) == dsu0.f(j)){
				return false;
			}
			if(p[i][j] == 2 && dsu1.f(i) == dsu1.f(j)){
				return false;
			}
		}
	}
	map<int, vector<int>> p1, p2;
	for(int i = 0; i < n; i++){
		p1[dsu1.f(i)].push_back(i);
	}
	for(auto [i, v] : p1){
		for(int j = 1; j < v.size(); j++){
			answer[v[0]][v[j]] = answer[v[j]][v[0]] = 1;
		}
		p2[dsu0.f(v[0])].push_back(v[0]);
	}
	for(auto [i, v] : p2){
		if(v.size() == 1) continue;
		if(v.size() == 2) return false;
		for(int j = 1; j < v.size(); j++){
			answer[v[j - 1]][v[j]] = answer[v[j]][v[j - 1]] = 1;
		}
		answer[v[0]][v[v.size() - 1]] = answer[v[v.size() - 1]][v[0]] = 1;
	}
	build(answer);
	return true;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:55:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |  for(auto [i, v] : p1){
      |           ^
supertrees.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int j = 1; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
supertrees.cpp:61:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |  for(auto [i, v] : p2){
      |           ^
supertrees.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j = 1; j < v.size(); j++){
      |                  ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4