Submission #411082

#	Time	Username	Problem	Language	Result	Execution time	Memory
411082		eagle30	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	268 ms	30292 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int visited[2000], hi[1000000];
vector<vector<int> > adjlist;
int coun=1;
void dfs(int s){
	visited[s]=coun;
	for(int i=0; i<adjlist[s].size(); i++){
		int v=adjlist[s][i];
		if(visited[v]==0)
			dfs(v);
	}
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	adjlist.assign(n+1, vector<int>());
	bool is=false;
	set<int> si;
	for(int i=0; i<n; i++){		
		for(int j=0; j<n; j++){
			if(p[i][j] && i!=j){
				si.insert(p[i][j]);
				if(p[i][j]==2)
					hi[i]=1, hi[j]=1;
				adjlist[i].push_back(j);
				adjlist[j].push_back(i);
			}
			if(p[i][j]==2)
				is=true;
		}
	}
	for(int i=0; i<n; i++){
		if(visited[i]==0){
			dfs(i);
			coun++;
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(visited[i]==visited[j] && p[i][j]==0)
				return 0;
		}
	}
	vector<vector<int> > answer;
	answer.assign(n, vector<int>());
	for(int i=0; i<n; i++)
		answer[i].assign(n, 0);
	map<int, vector<int> > mp;
	for(int i=0; i<n; i++)
		mp[visited[i]].push_back(i);
	if(si.size()<=1){
		for(auto x:mp){
			for(int i=1; i<x.second.size(); i++){
				answer[x.second[i-1]][x.second[i]]=1;
				answer[x.second[i]][x.second[i-1]]=1;
			}
			if(is){
				if(x.second.size()==1)
					continue;
				if(x.second.size()==2)
					return 0;
				answer[x.second[0]][x.second[x.second.size()-1]]=1;
				answer[x.second[x.second.size()-1]][x.second[0]]=1;
			}
		}
	}
	else{
		for(auto x:mp){
			vector<int> vi;
			int asdf;
			for(int i=0; i<x.second.size(); i++){
				if(hi[x.second[i]])
					vi.push_back(x.second[i]);
			}
			asdf=vi.size();
			for(int i=0; i<x.second.size(); i++)
				if(!hi[x.second[i]])
					vi.push_back(x.second[i]);
			for(int i=1; i<vi.size(); i++){
				answer[vi[i-1]][vi[i]]=1;
				answer[vi[i]][vi[i-1]]=1;
			}
			answer[vi[0]][vi[asdf-1]]=1;
			answer[vi[asdf-1]][vi[0]]=1;
		}
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:9:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for(int i=0; i<adjlist[s].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int i=1; i<x.second.size(); i++){
      |                 ~^~~~~~~~~~~~~~~~
supertrees.cpp:72:18: 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<x.second.size(); i++){
      |                 ~^~~~~~~~~~~~~~~~
supertrees.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int i=0; i<x.second.size(); i++)
      |                 ~^~~~~~~~~~~~~~~~
supertrees.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int i=1; i<vi.size(); i++){
      |                 ~^~~~~~~~~~

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