Submission #340626

#	Time	Username	Problem	Language	Result	Execution time	Memory
340626		todaybrian	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	283 ms	24172 KiB

supertrees

#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);

//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;
//}

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