Submission #302887

#	Time	Username	Problem	Language	Result	Execution time	Memory
302887		ivan24	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	1 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];
    }
};

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

Compilation message (stderr)

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