Submission #526225

#	Time	Username	Problem	Language	Result	Execution time	Memory
526225		pokmui9909	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	259 ms	24060 KiB

supertrees

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

class UnionFind{
public:
	UnionFind(ll S){
		p.resize(S + 5, -1);
	}
	ll Find(ll n){
		if (p[n] < 0) return n;
		else return p[n] = Find(p[n]);
	}
	void Union(ll a, ll b){
		a = Find(a), b = Find(b);
		if (a == b) return;
        p[a] += p[b];
		p[b] = a;
    }
	bool Same(ll a, ll b) { return Find(a) == Find(b); }
	ll Size(ll n) { return -p[Find(n)]; }
    bool Root(ll n) {return n == Find(n);}
private:
	vector<ll> p;
};
ll N; 
vector<ll> A;

int construct(std::vector<std::vector<int>> P) {
	N = P.size();
    vector<vector<int>> T(N, vector<int>(N));
    auto add_edge = [&](ll u, ll v) -> void{
        T[u][v] = T[v][u] = 1;
    };
    UnionFind S1(N), S2(N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(P[i][j] == 3){
                return 0;
            }
            if(j >= i || P[i][j] == 0) continue;
            S1.Union(i, j);
            if(P[i][j] == 1){
                S2.Union(i, j);
            }
        }
    }
    for(int i = 0; i < N; i++){
        if(!S2.Root(i)){
            add_edge(S2.Find(i), i);
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            if(S2.Same(i, j) && P[i][j] != 1){
                return 0;
            } else if(S1.Same(i, j) && P[i][j] != 2 && P[i][j] != 1){
                return 0;
            }
        }
    }
    for(int i = 0; i < N; i++){
        if(!S1.Root(i)) continue;
        A.clear();
        for(int j = 0; j < N; j++){
            if(S1.Same(i, j) && S2.Root(j)){
                A.push_back(j);
            }
        }
        if(A.size() == 2) return 0;
        if(A.size() == 1) continue;
        for(int j = 0; j < A.size(); j++){
            add_edge(A[j], A[(j == A.size() - 1 ? 0 : j + 1)]);
        }
    }
    build(T);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 0; j < A.size(); j++){
      |                        ~~^~~~~~~~~~
supertrees.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             add_edge(A[j], A[(j == A.size() - 1 ? 0 : j + 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