| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 301846 | Pro100Yan | 식물 비교 (IOI20_plants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
#include <iostream>
#define ll long long
#define pb push_back
using namespace std;
const int N = 20005;
vector<vector<int>> ans;
int d[N], used[N];
int get_parent(int v){
if(v == d[v])
return v;
return d[v] = get_parent(d[v]);
}
void add(int u, int v){
int f = get_parent(u), s = get_parent(v);
if(f != s)
d[f] = d[s];
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
int fault = 0;
for(int i = 0; i < n; i++)
d[i] = i;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
ans.push_back(row);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j]){
add(i, j);
}
}
}
int pi, pj;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
pi = get_parent(i);
pj = get_parent(j);
if(p[i][j]){
if(pi != pj)
return 0;
if(pi != i)
ans[i][pi] = ans[pi][i] = 1;
if(pi != j)
ans[j][pi] = ans[pi][j] = 1;
}
else{
if(pi == pj)
return 0;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 2){
pi = get_parent(i);
if(used[pi] || pi == i || pi == j)
continue;
ans[i][j] = ans[j][i] = 1;
used[pi] = 1;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(p[i][j] == 2){
pi = get_parent(i);
if(!used[pi])
return 0;
}
}
}
build(ans);
return 1;
}
/*
5
1 1 0 0 0
1 1 0 0 0
0 0 1 2 2
0 0 2 1 2
0 0 2 2 1
*/