Submission #948009

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948009	2024-03-17T12:28:10 Z	4QT0R	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define loop(a,b,c) for(int a = b; a<c; a++)

struct DSU{
	vi leader;
	vi siz;

	void init(int n){
		leader.resize(n+1);
		siz.resize(n+1);
		for (int i = 0; i<n; i++){
			leader[i]=i;
			siz[i]=1;
		}
	}
	
	int Find(int v){
		if (leader[v]==v)return v;
		leader[v]=Find(leader[v]);
		return leader[v];
	}

	bool same_set(int a, int b){
		return Find(a)==Find(b);
	}

	void Union(int a, int b){
		a=Find(a);
		b=Find(b);
		if (a==b)return;
		if (siz[a]<siz[b])swap(a,b);
		leader[b]=a;
		siz[a]+=siz[b];
	}
};

bool vis_branch[1502];
bool vis_comp[1502];
int nr_branch[1502];
int nr_comp[1502];
int wyn[1503][1503];

int construct(vvi p){
	int n=p.size();

	DSU compound,branch;
	compound.init(n);
	branch.init(n);
	loop(i,0,n){
		loop(j,0,n){
			if (p[i][j]){
				if (p[i][j]==3)return 0;
				compound.Union(i,j);
				if (p[i][j]==1)branch.Union(i,j);
			}
		}
	}
	loop(i,0,n){
		loop(j,i+1,n){
			if (p[i][j]==0 && compound.same_set(i,j))return 0;
			if (p[i][j]==2 && branch.same_set(i,j))return 0;
		}
	}
	vvi single;
	vvi cycle;
	int iter=0,iter2=0;
	loop(i,0,n){
		if (!vis_branch[branch.Find(i)]){
			if (!vis_comp[compound.Find(i)]){
				vis_comp[compound.Find(i)]=true;
				cycle.push_back({i});
				nr_comp[compound.Find(i)]=iter2++;
			}
			else cycle[nr_comp[compound.Find(i)]].push_back(i);
			vis_branch[branch.Find(i)]=true;
			single.push_back({i});
			nr_branch[branch.Find(i)]=iter++;
		}
		else single[nr_branch[branch.Find(i)]].push_back(i);
	}
	loop(i,0,iter){
		loop(j,1,single[i].size()){
			wyn[single[i][0]][single[i][j]]=wyn[single[i][j]][single[i][0]]=1;
		}
	}
	loop(i,0,iter2){
		if (cycle[i].size()==1)continue;
		else if (cycle[i].size()==2)return 0;
		wyn[cycle[i][0]][cycle[i].back()]=wyn[cycle[i].back()][cycle[i][0]]=1;
		loop(j,1,cycle[i].size()){
			wyn[cycle[i][j-1]][cycle[i][j]]=wyn[cycle[i][j]][cycle[i][j-1]]=1;
		}
	}
	build(wyn);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:6:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define loop(a,b,c) for(int a = b; a<c; a++)
......
   86 |   loop(j,1,single[i].size()){
      |        ~~~~~~~~~~~~~~~~~~~~          
supertrees.cpp:86:3: note: in expansion of macro 'loop'
   86 |   loop(j,1,single[i].size()){
      |   ^~~~
supertrees.cpp:6:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define loop(a,b,c) for(int a = b; a<c; a++)
......
   94 |   loop(j,1,cycle[i].size()){
      |        ~~~~~~~~~~~~~~~~~~~           
supertrees.cpp:94:3: note: in expansion of macro 'loop'
   94 |   loop(j,1,cycle[i].size()){
      |   ^~~~
supertrees.cpp:98:8: error: could not convert '(int (*)[1503])(& wyn)' from 'int (*)[1503]' to 'std::vector<std::vector<int> >'
   98 |  build(wyn);
      |        ^~~
      |        |
      |        int (*)[1503]