Submission #304471

#	Time	Username	Problem	Language	Result	Execution time	Memory
304471		SorahISA	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	263 ms	22268 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> par(maxn), cc[maxn];

int R(int x) {return par[x] ^ x ? par[x] = R(par[x]) : x;}
void U(int x, int y) {par[R(x)] = R(y);}

int construct(vector<vector<int>> p) {
    iota(ALL(par), 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]) U(i, j);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        cc[R(i)].eb(i);
        for (int j = 0; j < n; ++j) {
            if (!p[i][j] and R(i) == R(j)) return 0;
        }
    }
    
    for (int i = 0; i < n; ++i) {
        int sz = cc[i].size();
        for (int j = 0; j < sz-1; ++j) {
            ans[cc[i][j]][cc[i][j+1]] = 1;
            ans[cc[i][j+1]][cc[i][j]] = 1;
        }
        if (sz == 2) return 0;
        if (sz > 1) {
            ans[cc[i][0]][cc[i][sz-1]] = 1;
            ans[cc[i][sz-1]][cc[i][0]] = 1;
        }
    }
    
    build(ans);
    return 1;
}

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