Submission #302910

#	Time	Username	Problem	Language	Result	Execution time	Memory
302910		ivan24	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	0 ms	256 KiB

supertrees

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

using ll = int;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

class UnionFind {
private:
    ll n;
    vi p,sz;
public:
    UnionFind(ll n): n(n),p(n),sz(n,1){
        for (ll i = 0; n > i; i++) p[i] = i;
    }
    ll root(ll x){
        if (x != p[x]) p[x] = root(p[x]);
        return p[x];
    }
    void unify (ll x, ll y){
        x = root(x), y = root(y);
        if(x == y) return;
        if (sz[x] < sz[y]) swap(x,y);
        p[y] = x; sz[x] += sz[y];
    }
};

void build(vvi b);

int construct(vvi p) {
	int n = p.size();
	vvi ans(n,vi(n,0));
	vi hasSet(n,0);
	for (int i = 0; n > i; i++){
        if (hasSet[i]) continue;
	    vi cur_set;
        for (ll j = 0; n > j; j++){
            if (p[i][j] != 0){
                cur_set.push_back(j);
                if (hasSet[j]) return 0;
                else hasSet[j] = 1;
            }
        }
        for (auto j: cur_set){
            for (auto k: cur_set){
                if (j == k) continue;
                if (p[j][k] == 0) return 0;
                else p[j][k] = 0;
            }
        }
        if (cur_set.size() == 1) continue;
        for (ll j = 0; cur_set.size() > j; j++){
            //ans[i][cur_set[j]] = ans[cur_set[j]][i] = 1;
            ans[cur_set[j]][cur_set[(j+1)%n]] = ans[cur_set[(j+1)%n]][cur_set[j]] = 1;
        }
	}
	for (ll i = 0; n > i; i++){
        for (ll j = 0; n > j; j++){
            if (p[i][j] && i != j) return 0;
        }
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(vvi)':
supertrees.cpp:58:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   58 |         for (ll j = 0; cur_set.size() > j; j++){
      |                        ~~~~~~~~~~~~~~~^~~

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