Submission #411069

#	Time	Username	Problem	Language	Result	Execution time	Memory
411069		eagle30	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	256 ms	32060 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int visited[2000];
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;
	for(int i=0; i<n; i++){		
		for(int j=0; j<n; j++){
			if(p[i][j] && i!=j){
				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);
	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;
		}
	}
	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:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=1; i<x.second.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