Submission #382902

#	Time	Username	Problem	Language	Result	Execution time	Memory
382902		danielcm585	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	287 ms	22380 KiB

supertrees

#include "supertrees.h"

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

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;

const int N = 1e3;
int dsu[3][N+2];

int find(int idx, int x) {
    if (dsu[idx][x] == x)
        return x;
    return dsu[idx][x] = find(idx,dsu[idx][x]);
}

void merge(int idx, int a, int b) {
    int ra = find(idx,a);
    int rb = find(idx,b);
    dsu[idx][ra] = rb;
}

bool connect(int idx, int a, int b) {
    return (find(idx,a) == find(idx,b));
}

int construct(vector<vector<int>> p) {
	int n = p.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 2; j++) {
            dsu[j][i] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (p[i][j] == 3)
                return 0;
            if (p[i][j] != 0)
                merge(0,i,j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 0 && connect(0,i,j))
                return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 1)
                merge(1,i,j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 2 && connect(1,i,j))
                return 0;
        }
    }
	vector<vector<int>> ans(n,vector<int>(n,0));
    for (int i = 0; i < n; i++) {
        int r = find(1,i);
        if (r != i) {
            ans[i][r] = 1;
            ans[r][i] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int u = find(1,i);
            int v = find(1,j);
            if (p[u][v] == 2)
                merge(2,u,v);
        }
    }
    vector<vector<int>> ls(n);
    for (int i = 0; i < n; i++) {
        ls[find(2,i)].pb(i);
    }
    for (int i = 0; i < n; i++) {
        int sz = ls[i].size();
        if (sz <= 1)
            continue;
        if (sz == 2)
            return 0;
        for (int j = 0; j < sz; j++) {
            int u = ls[i][(j+1)%sz];
            int v = ls[i][j];
            ans[u][v] = 1;
            ans[v][u] = 1;
        }
    }
    // Subsoal 3
    // vector<vector<int>> ls(n);
    // for (int i = 0; i < n; i++) {
    //     ls[find(i)].pb(i);
    // }
    // for (int i = 0; i < n; i++) {
    //     int sz = ls[i].size();
    //     if (sz <= 1)
    //         continue;
    //     if (sz == 2)
    //         return 0;
    //     for (int j = 0; j < sz; j++) {
    //         int u = ls[i][(j+1)%sz];
    //         int v = ls[i][j];
    //         ans[u][v] = 1;
    //         ans[v][u] = 1;
    //     }
    // }
    // Subsoal 1
    // for (int i = 1; i < n; i++) {
    //     ans[i-1][i] = 1;
    //     ans[i][i-1] = 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