Submission #420152

#	Time	Username	Problem	Language	Result	Execution time	Memory
420152		Belgutei	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	506 ms	24016 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>

using namespace std;

#define mk make_pair
#define ff first
#define ss second
#define pb push_back

map<int,int> mp;
vector<int> tree[1005];


int construct(std::vector<std::vector<int> > p) {
	int n=p.size();
	std::vector<std::vector<int> > answer;
	answer.resize(n);
	bool c1=0,cc=0;
	for(int i=0; i<p.size(); i++){
		for(int j=0; j<p[i].size(); j++){
			answer[i].resize(n);
			if(p[i][j]>=2) c1=1;
			if(i==j) continue;
			if(p[i][j]==1 || p[i][j]==3) cc=1;
		}
	}
	if(c1==0){
		// subtask 1,2
		int cnt=0;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j) continue;
				if(p[i][j]==1){
					if(mp[i]==0 && mp[j]==0){
						cnt++;
						mp[i]=cnt;
						mp[j]=cnt;
						tree[cnt].pb(i);
						tree[cnt].pb(j);
						continue;
					}
					if(mp[i]==0){
						mp[i]=mp[j];
						tree[mp[i]].pb(i);
						continue;
					}
					if(mp[j]==0){
						mp[j]=mp[i];
						tree[mp[j]].pb(j);
						continue;
					}
					if(mp[i]!=mp[j]) return 0;
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j) continue;
				if(mp[i]!=mp[j] && p[i][j]==1) return 0;
				if(mp[i]==mp[j] && p[i][j]==0 && mp[i]!=0) return 0;
			}
		}
		for(int i=1; i<=cnt; i++){
			for(int j=1; j<tree[i].size(); j++){
				answer[tree[i][j]][tree[i][j-1]]=1;
				answer[tree[i][j-1]][tree[i][j]]=1;
			}
		}
		build(answer);
		return 1;
	}
	if(cc==0){
		// subtask 2
		int cnt=0;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j) continue;
				if(p[i][j]==2){
					if(mp[i]==0 && mp[j]==0){
						cnt++;
						mp[i]=cnt;
						mp[j]=cnt;
						tree[cnt].pb(i);
						tree[cnt].pb(j);
						continue;
					}
					if(mp[i]==0){
						mp[i]=mp[j];
						tree[mp[i]].pb(i);
						continue;
					}
					if(mp[j]==0){
						mp[j]=mp[i];
						tree[mp[j]].pb(j);
						continue;
					}
					if(mp[i]!=mp[j]) return 0;
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j) continue;
				if(mp[i]!=mp[j] && p[i][j]==2) return 0;
				if(mp[i]==mp[j] && p[i][j]==0 && mp[i]!=0) return 0;
			}
		}
		for(int i=1; i<=cnt; i++){
			if(tree[i].size()==2) return 0;
			for(int j=1; j<tree[i].size(); j++){
				answer[tree[i][j]][tree[i][j-1]]=1;
				answer[tree[i][j-1]][tree[i][j]]=1;
			}
			answer[tree[i][0]][tree[i][tree[i].size()-1]]=1;
			answer[tree[i][tree[i].size()-1]][tree[i][0]]=1;
			
		}
		build(answer);
		return 1;
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<p.size(); i++){
      |               ~^~~~~~~~~
supertrees.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int j=0; j<p[i].size(); j++){
      |                ~^~~~~~~~~~~~
supertrees.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int j=1; j<tree[i].size(); j++){
      |                 ~^~~~~~~~~~~~~~~
supertrees.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int j=1; j<tree[i].size(); j++){
      |                 ~^~~~~~~~~~~~~~~

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