Submission #619816

#	Time	Username	Problem	Language	Result	Execution time	Memory
619816		KLPP	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	285 ms	47244 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)

class DSU{
	int sz[1000000];
	int parent[1000000];
	int n;
	public:
	void init(int N){
		n=N;
		rep(i,0,n)sz[i]=1,parent[i]=i;
	}
	int root(int x){
		if(x==parent[x])return x;
		parent[x]=root(parent[x]);
		return parent[x];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a]+=sz[b];
		parent[b]=a;
	}
};
DSU D;
DSU D2;
vector<int> comp[1000000];
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	
	D.init(n);
	rep(i,0,n){
		rep(j,0,n){
			if(p[i][j]==3)return 0;
			if(p[i][j]==1)D.merge(i,j);
		}
	}
	rep(i,0,n)comp[D.root(i)].push_back(i);
	rep(i,0,n){
		bool B=true;
		rep(j,i+1,n){
			if(D.root(j)==D.root(i)){
				B=false;
				if(p[i][j]!=1){
					return 0;
				}
			}
		}
		if(B){
			rep(j,0,i){
				if(D.root(j)==D.root(i))answer[i][j]=1,answer[j][i]=1;
			}
		}
	}
	D2.init(n);
	rep(i,0,n){
		rep(j,0,n){
			if(p[i][j]==2){
				D2.merge(D.root(i),D.root(j));
			}
		}
	}
	vector<pair<int,int> >V;
	rep(i,0,n){
		if(D.root(i)==i){
			V.push_back({D2.root(i),i});
		}
	}
	sort(V.begin(),V.end());
	int bg=V[0].second;
	rep(i,0,V.size()){
		if(i<V.size()-1 && V[i].first==V[i+1].first){
			answer[V[i].second][V[i+1].second]=1;
			answer[V[i+1].second][V[i].second]=1;
		}else{
			if(answer[V[i].second][bg]==1){
				return 0;
			}else{
				answer[V[i].second][bg]=1;
				answer[bg][V[i].second]=1;
			}
			if(i<V.size())bg=V[i+1].second;
		}
	}
	rep(i,0,n){
		rep(j,0,n){
			if(p[i][j]==0 && D2.root(D.root(i))==D2.root(D.root(j))){
				//cout<<D2.root(D.root(i))<<" "<<D2.root(D.root(j))<<endl;
				return 0;
			}
		}
	}
	rep(i,0,n)answer[i][i]=0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
   84 |  rep(i,0,V.size()){
      |      ~~~~~~~~~~~~                
supertrees.cpp:84:2: note: in expansion of macro 'rep'
   84 |  rep(i,0,V.size()){
      |  ^~~
supertrees.cpp:85:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if(i<V.size()-1 && V[i].first==V[i+1].first){
      |      ~^~~~~~~~~~~
supertrees.cpp:95:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    if(i<V.size())bg=V[i+1].second;
      |       ~^~~~~~~~~

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