| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 393091 | abdzag | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include"supertrees.h"
#define rep(i,a,b) for(int i=a;i<int(b);i++)
#define rrep(i,a,b)for(int i=a;i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto& a: v)
typedef long long ll;
using namespace std;
const long long inf = 1e15;
vector<ll> p(2001);
vector<ll> Rank(2001);
ll Ufindset(ll i) {
if (p[i] == i)return i;
return p[i] = Ufindset(p[i]);
}
void UjoinSet(ll i, ll j) {
ll si = Ufindset(i);
ll sj = Ufindset(j);
if (sj == si)return;
if ( Rank[sj]> Rank[si])swap(sj, si);
p[sj] = si;
if (Rank[sj] == Rank[si]) Rank[si]++;
}
int constrct(vector<vector<int>> v) {
rep(i, 0, 2001)p[i] = i;
rep(i, 0, v.size()) {
rep(j, 0, v.size()) {
if (v[i][j]) UjoinSet(i, j);
}
}
vector<vector<int>> b(v.size(), vector<int>(v.size()));
rep(i, 0, v.size()) {
if (p[i] != i) {
b[i][p[i]]=1;
b[p[i]][i] = 1;
}
}
vector<vector<int>> check(v.size(), vector<int>(v.size()));
rep(i, 0, v.size()) {
vector<int> curvec(v.size());
queue<ll> q;
q.push(i);
while (!q.empty()) {
ll cur = q.front();
curvec[cur] = 1;
trav(a, b[cur])if (!curvec[a])q.push(a);
}
check[i] = curvec;
}
if (b != check)return 0;
build(b);
return 1;
}