제출 #1291631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291631		ChuanChen	슈퍼트리 잇기 (IOI20_supertrees)	C++20	21 / 100	101 ms	22032 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(v) cout << #v << ": " << v << endl;

const int MAXN = 1e3+3;

int n;
vector<vector<int>> ans;


int rep[MAXN], sz[MAXN];
int find(int no){
    if(rep[no] == no) return no;
    return rep[no] = find(rep[no]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    rep[b] = a;
}

int construct(vector<vector<int>> p) {
	n = p.size();
    ans.assign(n, vector<int>(n, 0));
	for(int i = 0; i < n; i++){
        sz[i] = 1; rep[i] = i;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 0) continue;
            if(find(i) != find(j)){
                merge(i, j);
                ans[j][i] = ans[i][j] = 1;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 0){
                if(find(i)==find(j)) return 0;
            }
        }
    }
    build(ans);
    return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4