oj.uz

답안 #507454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
507454 2022-01-12T13:04:12 Z jamezzz 슈퍼트리 잇기 (IOI20_supertrees) C++17
56 / 100
 226 ms 22236 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

struct ufds{
	int par[1005],rnk[1005];
	void init(int n){
		for(int i=0;i<n;++i)par[i]=i,rnk[i]=0;
	}
	int fp(int i){return (par[i]==i)?i:par[i]=fp(par[i]);}
	void join(int x,int y){
		x=fp(x),y=fp(y);
		if(x==y)return;
		if(rnk[x]==rnk[y])par[x]=y;
		else par[y]=x;
		if(rnk[x]==rnk[y])++rnk[x];
	}
}u;

int construct(vector<vector<int>> p){
	int n=p.size();
	u.init(n);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(p[i][j]==3)return 0;
			if(p[i][j]!=p[j][i])return 0;
			if(p[i][j]!=0)u.join(i,j);
		}
	}
	vector<vector<int>> c1;
	c1.resize(n);
	for(int i=0;i<n;++i){
		c1[u.fp(i)].push_back(i);
		for(int j=0;j<n;++j){
			if(u.fp(i)==u.fp(j)&&p[i][j]==0){
				return 0;
			}
		}
	}

	u.init(n);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(p[i][j]==1)u.join(i,j);
		}
	}
	vector<vector<int>> c2,c3;
	c2.resize(n);
	c3.resize(n);
	for(int i=0;i<n;++i){
		c2[u.fp(i)].push_back(i);
		for(int j=0;j<n;++j){
			if(u.fp(i)==u.fp(j)&&p[i][j]!=1){
				return 0;
			}
		}
		for(int j:c1[i]){
			if(u.fp(j)==j)c3[i].push_back(j);
		}
	}
	
	vector<vector<int>> answer;
	answer.resize(n);
	for(int i=0;i<n;++i)answer[i].resize(n);
	for(int i=0;i<n;++i){
		for(int j:c2[i]){
			if(i!=j)answer[i][j]=answer[j][i]=1;
		}
	}
	for(int i=0;i<n;++i){
		if(c3[i].size()>=2){
			int m=c3[i].size();
			for(int j=0;j<m;++j){
				int a=c3[i][j],b=c3[i][(j+1)%m];
				if(a!=b)answer[a][b]=answer[b][a]=1;
			}
		}
	}
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 196 ms 22128 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 196 ms 22128 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 9 ms 1100 KB Output is correct
13 Correct 184 ms 22236 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 5 ms 584 KB Output is correct
17 Correct 96 ms 8192 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 53 ms 5768 KB Output is correct
21 Correct 200 ms 22016 KB Output is correct
22 Correct 187 ms 22084 KB Output is correct
23 Correct 199 ms 22016 KB Output is correct
24 Correct 189 ms 22140 KB Output is correct
25 Correct 70 ms 8132 KB Output is correct
26 Correct 69 ms 8208 KB Output is correct
27 Correct 217 ms 22044 KB Output is correct
28 Correct 185 ms 22084 KB Output is correct

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 49 ms 5768 KB Output is correct
5 Correct 194 ms 22132 KB Output is correct
6 Correct 197 ms 22116 KB Output is correct
7 Correct 218 ms 22136 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 50 ms 5824 KB Output is correct
10 Correct 196 ms 22144 KB Output is correct
11 Correct 197 ms 22148 KB Output is correct
12 Correct 193 ms 22144 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 48 ms 5736 KB Output is correct
17 Correct 226 ms 22144 KB Output is correct
18 Correct 201 ms 22100 KB Output is correct
19 Correct 194 ms 22140 KB Output is correct
20 Correct 179 ms 22156 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 196 ms 22128 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 9 ms 1100 KB Output is correct
13 Correct 184 ms 22236 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 5 ms 584 KB Output is correct
17 Correct 96 ms 8192 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 53 ms 5768 KB Output is correct
21 Correct 200 ms 22016 KB Output is correct
22 Correct 187 ms 22084 KB Output is correct
23 Correct 199 ms 22016 KB Output is correct
24 Correct 189 ms 22140 KB Output is correct
25 Correct 70 ms 8132 KB Output is correct
26 Correct 69 ms 8208 KB Output is correct
27 Correct 217 ms 22044 KB Output is correct
28 Correct 185 ms 22084 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Incorrect 1 ms 204 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 196 ms 22128 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 9 ms 1100 KB Output is correct
13 Correct 184 ms 22236 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 5 ms 584 KB Output is correct
17 Correct 96 ms 8192 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 53 ms 5768 KB Output is correct
21 Correct 200 ms 22016 KB Output is correct
22 Correct 187 ms 22084 KB Output is correct
23 Correct 199 ms 22016 KB Output is correct
24 Correct 189 ms 22140 KB Output is correct
25 Correct 70 ms 8132 KB Output is correct
26 Correct 69 ms 8208 KB Output is correct
27 Correct 217 ms 22044 KB Output is correct
28 Correct 185 ms 22084 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Incorrect 1 ms 204 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -