Submission #597003

#	Time	Username	Problem	Language	Result	Execution time	Memory
597003		inventiontime	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	232 ms	24012 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();
    ufds ufds(n);

    bool possible = true;

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

    loop(i, n) loop(j, n) {
        if(p[i][j] != 1) if(!ufds.disjoint(i, j))
            possible = false;
    }

    if(!possible) return 0;

	vector<vi> ans(n, vi(n));
    loop(i, n) if(ufds.find(i) == i) {
        loop(j, n) {
            if(!ufds.disjoint(j, i)) if(i != j) {
                ans[i][j] = 1;
                ans[j][i] = 1;
            }
        }
    }
	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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4