Submission #1025705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025705		TheWilp	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	124 ms	24404 KiB

supertrees

#include "supertrees.h"
#include <vector>

int get_head(int u,std::vector<int>& d) {
	int p = d[u];
	while(d[p] != p) p = d[p];
	d[u] = p;
	return p;
}

int merge(int u,int v,std::vector<int>& d) {
	u = get_head(u,d);
	v = get_head(v,d);
	if(u == v) return v;
	d[u] =v;
	return v;
}

int construct(std::vector<std::vector<int>> p) {
	int N = p.size();
	std::vector<bool> check(N,false);
	std::vector<std::vector<int>> edges(N,std::vector<int>(N,0));
	for(int q = 0;q < N;q++) {
		for(int w = 0;w < N;w++) {
			if(p[q][w] == 3) {
				return 0;
			}
			if(q == w && p[q][w] != 1) return 0;
		}
	}
	auto check_chain = [&](std::vector<int> v) {
		// V should be sorted
		for(int q = 0;q < v.size();q++) {
			for(int w = 0;w < v.size();w++) {
				if(p[v[q]][v[w]] != 1) return false;
			}
		}
		for(int q = 0;q < v.size();q++) {
			int i = 0;
			for(int w = 0;w < N;w++) {
				if(i < v.size() && v[i] == w) {
					++i;
				}
				else if(p[v[q]][w] == 1 || p[w][v[q]] == 1) return false;
			}
		}
		return true;
	};
	auto build_chain = [&](std::vector<int> v) {
		for(int q = 0;q < v.size() - 1;q++){
			edges[v[q]][v[q + 1]] = 1;
			edges[v[q + 1]][v[q]] = 1;
		}
	};
	auto check_cycle = [&](std::vector<std::vector<int>> chains) {
		for(int q = 0;q < chains.size();q++) {
			for(int w = 0;w < chains.size();w++) {
				if(q == w) continue;
				for(int e = 0;e < chains[q].size();e++) {
					for(int r = 0;r < chains[w].size();r++) {
						if(p[chains[q][e]][chains[w][r]] != 2) return false;
					}
				}
			}
		}
		if(chains.size() == 2) return false;
		return true;
	};
	auto build_cycle = [&](std::vector<std::vector<int>> chains) {
		int N = chains.size();
		if(N == 1) return;
		for(int q = 0 ;q<chains.size();q++) {
			int x = chains[q][0];
			int y = chains[(q + 1) % N][0];
			edges[x][y] = 1;
			edges[y][x] = 1;
		}
	};
	
	std::vector<std::vector<int>> chains;
	std::vector<int> belong(N);
	for(int q = 0;q < N;q++) {
		if(!check[q]) {
			check[q] = true;
			chains.push_back(std::vector<int>());
			for(int w = 0;w < N;w++) {
				if(p[q][w] == 1) {
					chains.back().push_back(w);
					belong[w] = chains.size() - 1;
					check[w] = true;
				}
			}
			if(!check_chain(chains.back())) {
				return 0;
			}
			build_chain(chains.back());
		}
	}
	
	std::vector<int> d(chains.size(),0);
	for(int q = 0;q < d.size();q++) d[q] = q;
	for(int q = 0;q < N ;q++) {
		for(int w = 0;w < N;w++) {
			if(p[q][w] == 2) {
				merge(belong[q],belong[w],d);
			}	
		}
	}
	std::vector<std::vector<std::vector<int>>> group_chains(chains.size());
	for(int q = 0;q < chains.size();q++){
		group_chains[d[q]].push_back(chains[q]);
	}
	for(int q = 0;q < group_chains.size();q++) {
		if(group_chains[q].size()) {
			if(!check_cycle(group_chains[q])) return 0;
			else build_cycle(group_chains[q]);
		}
	}
	build(edges);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In lambda function:
supertrees.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int q = 0;q < v.size();q++) {
      |                 ~~^~~~~~~~~~
supertrees.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int w = 0;w < v.size();w++) {
      |                  ~~^~~~~~~~~~
supertrees.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int q = 0;q < v.size();q++) {
      |                 ~~^~~~~~~~~~
supertrees.cpp:41:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if(i < v.size() && v[i] == w) {
      |        ~~^~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int q = 0;q < v.size() - 1;q++){
      |                 ~~^~~~~~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int q = 0;q < chains.size();q++) {
      |                 ~~^~~~~~~~~~~~~~~
supertrees.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int w = 0;w < chains.size();w++) {
      |                  ~~^~~~~~~~~~~~~~~
supertrees.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int e = 0;e < chains[q].size();e++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |      for(int r = 0;r < chains[w].size();r++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int q = 0 ;q<chains.size();q++) {
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int q = 0;q < d.size();q++) d[q] = q;
      |                ~~^~~~~~~~~~
supertrees.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for(int q = 0;q < chains.size();q++){
      |                ~~^~~~~~~~~~~~~~~
supertrees.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int q = 0;q < group_chains.size();q++) {
      |                ~~^~~~~~~~~~~~~~~~~~~~~

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