Submission #597898

#	Time	Username	Problem	Language	Result	Execution time	Memory
597898		inventiontime	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	183 ms	24016 KiB

supertrees

#include "supertrees.h"

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

#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define re resize
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)
#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;
//const int maxn = ;

struct ufds {

    vi par;

    ufds(int n): par(n+1, -1) {}

    int find(int a) {
        while(par[a] >= 0)
            a = par[a];
        return a;
    }

    int size(int a) {
        return -par[find(a)];
    }

    bool disjoint(int a, int b) {
        a = find(a);
        b = find(b);
        return !(a == b);
    }

    bool merge(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return false;
        if(-par[a] < -par[b]) 
            swap(a, b);
        par[a] += par[b];
        par[b] = a;
        return true;
    }

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

};

int construct(vector<vi> p) {

    int n = p.size();

    bool possible = true;

    ufds ufds1(n);
    loop(i, n) loop(j, n) {
        if(p[i][j] == 1)
            ufds1.merge(i, j);
    }

    vi par(n);
    map<int, vi> groups;
    loop(i, n) {
        int x = ufds1.find(i);
        par[i] = x;
        if(x != i) groups[x].pb(i);
    }

    vi keys;
    loop(i, n) if(par[i] == i) {
        keys.pb(i);
    }

    loop(i, n) loop(j, n) {
        if(p[i][j] != p[par[i]][par[j]])
            possible = false;
        if(p[i][j] == 3) possible = false;
    }

    ufds ufds2(n);
    for(auto i : keys) for(auto j : keys) {
        if(p[i][j] == 2)
            ufds2.merge(i, j);
    }

    vi par2(n);
    map<int, vi> groups2;
    for(auto i : keys) {
        int x = ufds2.find(i);
        par2[i] = x;
        if(x != i) groups2[x].pb(i);
    }

    for(auto i : keys) for(auto j : keys) if(i != j) {
        if(p[i][j] != 2) if(!ufds2.disjoint(i, j))
            possible = false;
    }

    vector<vi> ans(n, vi(n));
    for(auto [node, grp] : groups) {
        for(auto x : grp) {
            ans[x][node] = 1;
            ans[node][x] = 1;
        }
    }

    for(auto [node, grp] : groups2) {
        if(grp.size() == 1) possible = false;
        int prev = node;
        for(auto x : grp) {
            ans[prev][x] = 1;
            ans[x][prev] = 1;
            prev = x;
        }
        ans[prev][node] = 1;
        ans[node][prev] = 1;
    }

    if(!possible) return 0;
    build(ans);

    return 1;

}

Compilation message (stderr)

supertrees.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   27 | const int inf = 1e17;
      |                 ^~~~

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