제출 #304490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
304490		SorahISA	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	273 ms	22284 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

const int maxn = 1000 + 5;

vector<int> par1(maxn), cc1[maxn], par2(maxn), cc2[maxn];

int R1(int x) {return par1[x] ^ x ? par1[x] = R1(par1[x]) : x;}
int R2(int x) {return par2[x] ^ x ? par2[x] = R2(par2[x]) : x;}
void U1(int x, int y) {par1[R1(x)] = R1(y);}
void U2(int x, int y) {par2[R2(x)] = R2(y);}

int construct(vector<vector<int>> p) {
    iota(ALL(par1), 0), iota(ALL(par2), 0);
    int n = p.size();
    vector<vector<int>> ans(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 3) return 0;
            if (p[i][j] == 1) U1(i, j);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        cc1[R1(i)].eb(i);
        for (int j = 0; j < n; ++j) {
            if (!p[i][j] and R1(i) == R1(j)) return 0;
        }
    }
    
    for (int i = 0; i < n; ++i) {
        int sz = cc1[i].size();
        for (int j = 0; j < sz-1; ++j) {
            ans[cc1[i][j]][cc1[i][j+1]] = 1;
            ans[cc1[i][j+1]][cc1[i][j]] = 1;
        }
    }
    
    for (int i = 0; i < n; ++i) R1(i);
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 2) U2(par1[i], par1[j]);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        if (par1[i] == i) {
            cc2[R2(i)].eb(i);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        int sz = cc2[i].size();
        for (int j = 0; j < sz; ++j) {
            for (int k = j+1; k < sz; ++k) {
                for (auto x : cc1[cc2[i][j]]) {
                    for (auto y : cc1[cc2[i][k]]) {
                        if (p[x][y] != 2) return 0;
                    }
                }
            }
        }
        
        for (int j = 0; j < sz-1; ++j) {
            ans[cc2[i][j]][cc2[i][j+1]] = 1;
            ans[cc2[i][j+1]][cc2[i][j]] = 1;
        }
        if (sz == 2) return 0;
        if (sz > 1) {
            ans[cc2[i][0]][cc2[i][sz-1]] = 1;
            ans[cc2[i][sz-1]][cc2[i][0]] = 1;
        }
    }
    
    build(ans);
    return 1;
}

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