Submission #377353

#	Time	Username	Problem	Language	Result	Execution time	Memory
377353		Thistle	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	325 ms	22380 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<algorithm>
#include<set>
#include<iostream>
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define vec vector
#define vi vec<ll>
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())

class unionfind{
	int n;
	vi pa,sz;
    public:
	unionfind(int n):n(n){
		pa.resize(n);
		sz.assign(n,1);
		rep(i,n) pa[i]=i;
	}
	int root(int x){
		if(pa[x]==x) return x;
		return pa[x]=root(pa[x]);
	}
	void unite(int x,int y){
		x=root(x);y=root(y);
		if(x==y) return;
		if(sz[x]>sz[y]) swap(x,y);
		sz[y]+=sz[x];
		pa[x]=y;
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();

	//hanteiwo suru

	unionfind uf(n);
	rep(i,n)rep(j,n){
		if(p[i][j]==3) return 0;
		if(p[i][j]) uf.unite(i,j); 
	}
	rep(i,n)rep(j,n){
		if(uf.root(i)==uf.root(j)&&p[i][j]==0){
			return 0;
		}
	}

	vec<vec<int>>answer(n,vec<int>(n,0));
	vec<int>used(n,-1);int time2=0;
	vec<bool>used2(n,0);
	vi used3(n,-1); int time=0;
	rep(x,n){
		if(~used[x]) continue;
		vi v;
		rep(i,n){
			if(p[i][x]) {
				v.pb(i);
				used[i]=time2;
			}
		}
		for(auto g:v)for(auto r:v){
			if(p[g][r]==0) return 0;
 		}
		for(auto g:v)rep(i,n){
			if(p[g][i]&&used[i]!=time2)  return 0;
		}
		time2++;

		//seihoukei desuka?
		
		vi cic;

		for(auto g:v){
			if(used2[g]) continue;
			vi u;
			for(auto r:v){
				if(p[g][r]==1){
					u.pb(r);
					used2[r]=1;
					used3[r]=time;
				}
			}
			//koitura ha hokani 1 wo motte inaika?
			for(auto g:u){
				rep(i,n){
					if(p[i][g]==1&&used3[i]!=time){
						return 0;
					}
					if(used3[i]==time&&p[i][g]!=1){
						return 0;
					}
				}
			}
			rep(i,siz(u)-1){
				answer[u[i]][u[i+1]]=answer[u[i+1]][u[i]]=1;
			}
			cic.pb(u[0]);
			time++;
		}

		rep(i,siz(cic)-1){
			answer[cic[i]][cic[i+1]]=answer[cic[i+1]][cic[i]]=1;
		}
		if(siz(cic)>1){
			answer[cic[0]][cic[siz(cic)-1]]=
				answer[cic[siz(cic)-1]][cic[0]]=1;
		}
	}

	build(answer);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In constructor 'unionfind::unionfind(int)':
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:24:3: note: in expansion of macro 'rep'
   24 |   rep(i,n) pa[i]=i;
      |   ^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:45:2: note: in expansion of macro 'rep'
   45 |  rep(i,n)rep(j,n){
      |  ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:45:10: note: in expansion of macro 'rep'
   45 |  rep(i,n)rep(j,n){
      |          ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:49:2: note: in expansion of macro 'rep'
   49 |  rep(i,n)rep(j,n){
      |  ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:49:10: note: in expansion of macro 'rep'
   49 |  rep(i,n)rep(j,n){
      |          ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:59:2: note: in expansion of macro 'rep'
   59 |  rep(x,n){
      |  ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:62:3: note: in expansion of macro 'rep'
   62 |   rep(i,n){
      |   ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:71:16: note: in expansion of macro 'rep'
   71 |   for(auto g:v)rep(i,n){
      |                ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:92:5: note: in expansion of macro 'rep'
   92 |     rep(i,n){
      |     ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:101:4: note: in expansion of macro 'rep'
  101 |    rep(i,siz(u)-1){
      |    ^~~
supertrees.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
supertrees.cpp:14:18: note: in expansion of macro 'rng'
   14 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
supertrees.cpp:108:3: note: in expansion of macro 'rep'
  108 |   rep(i,siz(cic)-1){
      |   ^~~

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