Submission #827048

#	Time	Username	Problem	Language	Result	Execution time	Memory
827048		minhcool	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	9 ms	14432 KiB

supertrees

//#define local
#ifndef local
#include "supertrees.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int sz1[N], rt1[N];

int sz2[N], rt2[N];

int root1(int x){
	return (x == rt1[x] ? x : rt1[x] = root1(rt1[x]));
}

void merge1(int x, int y){
	x = root1(x), y = root1(y);
	if(x == y) return;
	if(sz1[x] < sz1[y]) swap(x, y);
	sz1[x] += sz1[y];
	rt1[y] = x;
}

int root2(int x){
	return (x == rt2[x] ? x : rt2[x] = root2(rt2[x]));
}

void merge2(int x, int y){
	x = root2(x), y = root2(y);
	if(x == y) return;
	if(sz2[x] < sz2[y]) swap(x, y);
	sz2[x] += sz2[y];
	rt2[y] = x;
}

vector<int> vc1[N], vc2[N];

bool ok[N];

int construct(vector<vector<int>> p) {
	int n = p.size();
	for(int i = 0; i < n; i++){
		vc1[i].clear(), vc2[i].clear();
	}
	//int n = p.size();
	for(int i = 0; i < n; i++){
		rt1[i] = i, sz1[i] = 1;
		rt2[i] = i, sz2[i] = 1;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			if(p[i][j] == 0){
				if(root1(i) == root1(j)) return 0;
			//	if(root2(i) == root2(j)) return 0;
			}
			if(p[i][j] >= 1){
			//	if(root2(i) == root2(j)) return 0;
				merge1(i, j);
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			if(p[i][j] == 0){
				if(root1(i) == root1(j)) return 0;
			//	if(root2(i) == root2(j)) return 0;
			}
		}
	}
	for(int i = 0; i < n; i++) vc1[root1(i)].pb(i);
	vector<vector<int>> answer;
	answer.resize(n);
	for(int i = 0; i < n; i++) answer[i].resize(n);
	for(int i = 0; i < n; i++){
		if(root1(i) != i) continue;
		vector<int> v;
		bool has2 = 0;
		for(auto it : vc1[i]){
			bool ck2 = 1;
			for(auto it2 : vc1[i]) has2 |= (p[it][it2] == 2);
		}
		//for(auto it : vc1[i]) ok[it] = 0;
		//for(auto it : v) ok[it] = 1;
		//if(v.size() <= 1 && has2) return 0;
		if(!has2) continue;
		for(auto it : vc1[i]){
			for(auto it2 : vc2[i]){
				if(ok[it] || ok[it2] || it == it2) continue;
				if(p[it][it2] == 1) merge2(it, it2);
			}
		}
		for(auto it : vc1[i]) if(!ok[it]) vc2[root2(it)].pb(it);
		vector<int> v2;
		for(auto it : vc1[i]){
			if(ok[it] || root2(it) != it) continue;
			v2.pb(it);
			for(auto it2 : vc2[it]){
				for(auto it3 : vc2[it]){
					if(it2 == it3) continue;
					if(p[it2][it3] == 2) return 0;
				}
			}
		}
		//if(v2.size() > v.size()) return 0;
		for(int j = 0; j < v2.size(); j++){
			//answer[v[j]][v2[j]] = 1;
			for(auto it : vc2[v2[j]]){
				if(it == v2[j]) continue;
				answer[it][v2[j]] = answer[v2[j]][it] = 1;
			}
		}
		for(int j = 0; j < v2.size(); j++) answer[v2[j]][v2[(j + 1) % v2.size()]] = answer[v2[(j + 1) % v2.size()]][v2[j]] = 1;
	}
	build(answer);
	return 1;
}

#ifdef local
void process(){
	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
#endif

Compilation message (stderr)

supertrees.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:9: warning: unused variable 'ck2' [-Wunused-variable]
  104 |    bool ck2 = 1;
      |         ^~~
supertrees.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int j = 0; j < v2.size(); j++){
      |                  ~~^~~~~~~~~~~
supertrees.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int j = 0; j < v2.size(); j++) answer[v2[j]][v2[(j + 1) % v2.size()]] = answer[v2[(j + 1) % v2.size()]][v2[j]] = 1;
      |                  ~~^~~~~~~~~~~

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