Submission #305826

#	Time	Username	Problem	Language	Result	Execution time	Memory
305826		tincan	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	285 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;
bool vis[MAXN];
vector<int> ds1[MAXN], ds2[MAXN];
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); }
} st1, st2;
vector<int> thng[MAXN];
void build(vector<vector<int>> b);
inline 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(N, vector<int>(N, 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) st1.join(i, i2);
				st2.join(i, i2);
			}
		}
	}

	for (int i = 0; i < N; i++) for (int i2 = i + 1; i2 < N; i2++)
		if ((p[i][i2] == 0 && st2.find(i) == st2.find(i2)) || (p[i][i2] == 2 && st1.find(i) == st1.find(i2))) return 0;
	for (int i = 0; i < N; i++) {
		ds1[st1.find(i)].push_back(i);
		ds2[st2.find(i)].push_back(st1.find(i));
	}
	for (int i = 0; i < N; i++) {
		sort(ds2[i].begin(), ds2[i].end());
		auto end = unique(ds2[i].begin(), ds2[i].end());
		ds2[i].resize((int)(end - ds2[i].begin()));
		if (ds2[i].size() == 2) return 0;
	}

	for (int i = 0; i < N; i++) {
		for (int i2 = 1; i2 < ds1[i].size(); i2++) make(ds1[i][i2], ds1[i][i2 - 1], ans);
		for (int i2 = 1; i2 < ds2[i].size(); i2++) make(ds2[i][i2], ds2[i][i2 - 1], ans);
		if(ds2[i].size() > 1) make(ds2[i].front(), ds2[i].back(), ans);
	}
	build(ans); return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i2 = 1; i2 < ds1[i].size(); i2++) make(ds1[i][i2], ds1[i][i2 - 1], ans);
      |                    ~~~^~~~~~~~~~~~~~~
supertrees.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i2 = 1; i2 < ds2[i].size(); i2++) make(ds2[i][i2], ds2[i][i2 - 1], ans);
      |                    ~~~^~~~~~~~~~~~~~~

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