Submission #1083824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1083824	2024-09-04T08:31:16 Z	rayan_bd	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	130 ms	24148 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;

vector<int> par1(1001),sz1(1001,1),par2(1001),sz2(1001,1),par3(1001),sz3(1003,1);

int findPar1(int u){
	if(par1[u]==u) return u;
	return par1[u]=findPar1(par1[u]);
}

int findPar2(int u){
	if(par2[u]==u) return u;
	return par2[u]=findPar2(par2[u]);
}

int findPar3(int u){
	if(par3[u]==u) return u;
	return par3[u]=findPar3(par3[u]);
}

void unite1(int u,int v){
	int ulp=findPar1(u);
	int vlp=findPar1(v);
	if(ulp==vlp) return;
	if(sz1[ulp]>sz1[vlp]){
		par1[vlp]=ulp;
		sz1[ulp]+=sz1[vlp];
	}else{
		par1[ulp]=vlp;
		sz1[vlp]+=sz1[ulp];
	}
}

void unite2(int u,int v){
	int ulp=findPar2(u);
	int vlp=findPar2(v);
	if(ulp==vlp) return;
	if(sz2[ulp]>sz2[vlp]){
		par2[vlp]=ulp;
		sz2[ulp]+=sz2[vlp];
	}else{
		par2[ulp]=vlp;
		sz2[vlp]+=sz2[ulp];
	}
}

void unite3(int u,int v){
	int ulp=findPar3(u);
	int vlp=findPar3(v);
	if(ulp==vlp) return;
	if(sz3[ulp]>sz3[vlp]){
		par3[vlp]=ulp;
		sz3[ulp]+=sz3[vlp];
	}else{
		par3[ulp]=vlp;
		sz3[vlp]+=sz3[ulp];
	}
}

bool is_samee1(int u,int v){
	return findPar1(u)==findPar1(v);
}

bool is_samee2(int u,int v){
	return findPar2(u)==findPar2(v);
}


bool is_samee3(int u,int v){
	return findPar3(u)==findPar3(v);
}



int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> adj(n,vector<int>(n,0));

	// subtask 4

	for(int i=0;i<n;++i) par1[i]=par2[i]=par3[i]=i;

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]==2){
				unite2(i,j);
				unite3(i,j);
			}
		}
	}

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]==1&&sz2[i]==1&&sz2[j]==1){
				unite1(i,j);
				unite3(i,j);
			}
		}
	}



	vector<int> last_2(n+1,-1),first(n+1,-1),last_1(n+1,-1);


	for(int i=0;i<n;++i){
		// connecting the 2 ways road
		int ulp1=findPar2(i);
		if(last_2[ulp1]!=-1&&sz2[ulp1]>2){
			adj[i][last_2[ulp1]]=1;
			adj[last_2[ulp1]][i]=1;
		}
		if(first[ulp1]==-1) first[ulp1]=i;
		last_2[ulp1]=i;

		ulp1=findPar1(i);
		if(last_1[ulp1]!=-1&&sz1[ulp1]>1){
			adj[i][last_1[ulp1]]=1;
			adj[last_1[ulp1]][i]=1;
		}
		last_1[ulp1]=i;
	}

	for(int i=0;i<n;++i){
		int ulp=findPar2(i);
		if(sz2[ulp]>1) adj[last_2[ulp]][first[ulp]]=adj[first[ulp]][last_2[ulp]]=1;
	}

	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(p[i][j]==1&&!is_samee3(i,j)){
				unite3(i,j);
				adj[i][j]=adj[j][i]=1;

			}
		}
	}
/*
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			if(adj[i][j]>0){
				cout<<i<<" - "<<j<<'\n';
			}
		}
	}*/

	build(adj);
	
	return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	6 ms	1380 KB	Output is correct
7	Correct	118 ms	24148 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	6 ms	1380 KB	Output is correct
7	Correct	118 ms	24148 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1240 KB	Output is correct
13	Correct	119 ms	24148 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	33 ms	6408 KB	Output is correct
5	Correct	116 ms	24144 KB	Output is correct
6	Correct	117 ms	24148 KB	Output is correct
7	Correct	120 ms	24096 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	30 ms	6244 KB	Output is correct
10	Correct	122 ms	24144 KB	Output is correct
11	Correct	124 ms	24144 KB	Output is correct
12	Correct	130 ms	24144 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Incorrect	0 ms	348 KB	Too many ways to get from 0 to 4, should be 1 found no less than 2
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	6 ms	1380 KB	Output is correct
7	Correct	118 ms	24148 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1240 KB	Output is correct
13	Correct	119 ms	24148 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	6 ms	1380 KB	Output is correct
7	Correct	118 ms	24148 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1240 KB	Output is correct
13	Correct	119 ms	24148 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Submission #1083824

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0