| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 340624 | todaybrian | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
struct DSU {
vector<int> p; void init(int N) { p = vector<int>(N,-1); }
int get(int x) { return p[x] < 0 ? x : p[x] = get(p[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -p[get(x)]; }
bool merge(int x, int y) {
x = get(x), y = get(y); if (x == y) return 0;
if (p[x] > p[y]) swap(x,y);
p[x] += p[y]; p[y] = x; return 1;
}
} ds1, ds2;
//
//void build(vector<vector<int>> b){
// for(vector<int> a:b){
// for (int i = 0; i < a.size(); i++) {
// cout << a[i] << ' ';
// }
// cout << '\n';
// }
//}
int N;
int construct(vector<vector<int> > p){
N = p.size();
vector<vector<int>> b(N, vector<int>(N, 0));
ds1.init(N+1); ds2.init(N+1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(i==j) continue;
if(p[i][j]!=0) ds1.merge(i, j);
if(p[i][j]==3) return 0;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(i==j) continue;
if(p[i][j] ==0 && ds1.sameSet(i, j)) return 0;
}
}
for (int i = 0; i < N; i++) {
if(ds1.p[i]>=0) continue;
unordered_set<int> added;
for (int j = 0; j < N; j++) {
if(!ds1.sameSet(i, j)) continue;
for (int k = 0; k < N; k++) {
if(!ds1.sameSet(i, k) || j==k) continue;
if(p[j][k] == 1) {
ds2.merge(j, k);
}
}
}
for (int j = 0; j < N; j++) {
if(!ds1.sameSet(i, j)) continue;
if(ds2.get(j) == j) added.insert(j);
}
for (int j = 0; j < N; j++) {
if(ds2.get(j) != j || !added.count(j)) continue;
int prev = j;
for (int k = 0; k < N; k++) {
if(j==k || !ds2.sameSet(j, k)) continue;
if(p[j][k] !=1) return 0;
b[prev][k] = b[k][prev] = 1;
prev= k;
}
}
if(added.size()==2) return 0;
if(added.size()>=3){
int prev = -1, fst = -1;
for(auto it:added){
if(prev==-1) prev = it, fst = it;
else{
b[prev][it] = b[it][prev] = 1;
prev = it;
}
}
b[fst][prev] = b[prev][fst] = 1;
}
}
build(b);
return 1;
}
//int main(){
// cin >> N;
// vector<vector<int>> b(N, vector<int>(N, 0));
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// cin >> b[i][j];
// }
// }
// construct(b);
// return 0;
//}