Submission #903854

#	Time	Username	Problem	Language	Result	Execution time	Memory
903854		ByeWorld	슈퍼트리 잇기 (IOI20_supertrees)	C++14	96 / 100	211 ms	24356 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
using namespace std;
const int MAXN = 1e3+10;
const double SMALL = 1e-6;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;

int n;
bool tag[MAXN], done[MAXN];
vector <vector<int>> adj;
vector <int> cc[MAXN];

void bd(int x, int y){
	adj[x][y] = 1; adj[y][x] = 1;
}

struct DSU {
	int par[MAXN], siz[MAXN];
	void bd(){
		for(int i=0; i<n; i++){
			par[i] = i; siz[i] = 1;
			cc[i].pb(i);
		}
	}
	int f(int x){
		if(x == par[x]) return x;
		return par[x] = f(par[x]);
	}
	bool con(int x, int y){
		return f(x) == f(y);
	}
	void mer(int x, int y){
		if(con(x, y)) return;
		x = f(x); y = f(y);
		if(siz[x] > siz[y]) swap(x, y);
		par[x] = y; siz[y] += siz[x];
		for(auto in : cc[x]) cc[y].pb(in);
	}
} A;

int construct(vector<vector<int>> p) {
	n = p.size();
	vector <int> te(n);
	for(int i=0; i<n; i++) adj.pb(te);
	A.bd();

	for(int i = 0; i < n; i++) {
		if(done[i]) continue;
		for(int x=0; x<n; x++) tag[x] = 0;

		vector <int> vec; vec.pb(i); tag[i] = 1;
		for(int j=i+1; j < n; j++){
			if(p[i][j] == 1){
				vec.pb(j); tag[j] = 1;
			}	
		}
		//for(auto in : vec) cout << in << "pp\n";
		for(auto in : vec){
			//cout << in << " in\n";
			done[in] = 1;
			for(int x=0; x<n; x++){
				if(tag[x] && p[in][x] != 1) return 0; //harusnya 1
				if(!tag[x] && p[in][x] == 1) return 0;
			}
		}
		for(int i=0; i+1<vec.size(); i++){ // build
			bd(vec[i], vec[i+1]);
			A.mer(vec[i], vec[i+1]);
		}
	}
	// for(int i=0; i<n; i++){
	// 	for(int j=0; j<n; j++) cout << adj[i][j] << ' ';
	// 	cout << '\n';
	// }
	// for(int i=0; i<n; i++){
	// 	if(A.f(i) == i){
	// 		for(auto in : cc[i]) cout << i << ' ' << in << " in\n";
	// 	}
	// }

	for(int i=0; i<n; i++) done[i] = 0;
	for(int i = 0; i < n; i++) {
		if(i != A.f(i) || done[A.f(i)]) continue;
		for(int x=0; x<n; x++) tag[x] = 0;

		vector <int> vec; vec.pb(A.f(i));
		for(int j=i+1; j < n; j++){
			if(p[i][j] == 2 && A.f(j)==j){ // par nya aj
				vec.pb(j); 
			}	
		}

		if(vec.size() == 1) continue;
		if(vec.size() == 2) return 0;

		vector <int> node;
		for(auto x : vec){
			for(auto in : cc[x]){
				node.pb(in); tag[in] = 1;
			}
		}
		//for(auto in: node) cout << in << " node\n";

		for(auto x : node){ // udh pernah connect
			for(auto y : node){
				if(x==y) continue; 
				if(p[x][y]==2 && A.con(x, y)) return 0;
			}
		}
		//for(auto in : vec) cout << in << "pp\n";
		for(auto in : node){
			//cout << in << " in\n";
			done[A.f(in)] = 1;
			for(int x=0; x<n; x++){
				if(x==in) continue;
				if(tag[x] && !A.con(in, x) && p[in][x] != 2) return 0; //harusnya 1
				if(!tag[x] && p[in][x] == 2) return 0;
			}
		}

		vector <int> s;
		for(auto in : node){
			s.pb(A.f(in));
		}
		sort(s.begin(), s.end());
		s.resize(unique(s.begin(), s.end()) - s.begin());

		//for(auto in : s) cout << in << " s\n";
		
		for(int i=0; i+1<s.size(); i++){ // build
			bd(s[i], s[i+1]);
		}
		bd(s[0], s.back());
	}

	for(int i=0; i<n; i++) adj[i][i] = 0;
	build(adj);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0; i+1<vec.size(); i++){ // build
      |                ~~~^~~~~~~~~~~
supertrees.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for(int i=0; i+1<s.size(); i++){ // build
      |                ~~~^~~~~~~~~

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