제출 #927393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927393		VMaksimoski008	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	167 ms	22132 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
 
struct DSU {
    int n, comp;
    vector<int> par, size;
 
    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }
 
    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }
 
    bool uni(int u, int v) {
        u = get(u), v = get(v);
 
        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);
 
        size[u] += size[v];
        par[v] = u;
        comp--;
 
        return true;
    }
 
    int getComp() { return comp; }
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
};

vector<vector<int> > graph;
vector<bool> vis;
vector<int> G;

void dfs(int u) {
    vis[u] = 1;
    G.push_back(u);

    for(int &v : graph[u]) {
        if(vis[v]) continue;
        dfs(v);
    }
}
 
int construct(vector<vector<int> > p) {
    int n = p.size();
    vector<vector<int> > B(n, vector<int>(n));

    DSU dsu; dsu.config(n);

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(p[i][j] == 3) return 0;
            if(dsu.uni(i, j))
                B[i][j] = B[j][i] = 1;
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(dsu.sameSet(i, j) && p[i][j] == 0) return 0;
            else if(!dsu.sameSet(i, j) && p[i][j] > 0) return 0;
        }
    }

    build(B);
    return 1;
}

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