Submission #934139

#	Time	Username	Problem	Language	Result	Execution time	Memory
934139		raul2008487	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	186 ms	23636 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
struct DSU{
    vl par;
    vector<vector<ll>> e;
    void init(ll n){
        e.resize(n + 1);
        par.resize(n + 1);
        ll i;
        for(i = 0; i < n; i++){
            e[i].pb(i);
            par[i] = i;
        }
    }
    ll get(ll x){
        if(par[x] == x){
            return x;
        }
        return par[x] = get(par[x]);
    }
    bool connected(ll x, ll y){
        return (get(x) == get(y));
    }
    bool unite(ll a, ll b){
        a = get(a);
        b = get(b);
        if(a == b){return false;}
        if(e[a].size() < e[b].size()){
            swap(a, b);
        }
        par[b] = a;
        for(auto x: e[b]){
            e[a].pb(x);
            par[x] = a;
        }
        e[b].clear();
        return true;
    }
};
int construct(vector<vector<int>> p) {
	DSU dsu1, dsu2;
    ll n = p.size(), i, j;
    dsu1.init(n);
    dsu2.init(n);
    vector<vector<ll>> ans(n, vector<ll> (n, 0));
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 1){
                dsu1.unite(i, j);
            }
            if(p[i][j] == 3){
                //cout << "nisiryoz signal" << endl;
                return 0;
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] != 1 && dsu1.connected(i, j)){
                //cout << "1" << endl;
                return 0;
            }
        }
    }
//    for(i = 0; i < n; i++){cout << dsu1.get(i) << ' ';}cout << endl;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 2){
                if(dsu2.unite(dsu1.get(i), dsu1.get(j))){
//                    cout << dsu1.get(i) <<  ' ' << dsu1.get(j) << endl;
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(i == j){continue;}
            if(p[i][j] == 0 && (dsu1.connected(i, j) || dsu2.connected(i, j))){
                //cout << "2" << endl;
                return 0;
            }
            if(dsu1.connected(i, j) && dsu2.connected(i, j)){
                //cout << "signal 3" << endl;
                return 0;
            }
        }
    }
    vector<bool> used(n, 0), vis(n, 0);
    for(i = 0; i < n; i++){
        ll x = dsu2.get(i);
        if(dsu2.e[x].size() == 2){/*cout << "3" << endl;*/return 0;}
        if(dsu2.e[x].size() > 2 && !used[x]){
            for(j = 0;j < dsu2.e[x].size() - 1; j++){
                ans[dsu2.e[x][j]][dsu2.e[x][j + 1]] = 1;
                ans[dsu2.e[x][j + 1]][dsu2.e[x][j]] = 1;
            }
            //cout << "#" << endl;
            ans[dsu2.e[x][0]][dsu2.e[x].back()] = ans[dsu2.e[x].back()][dsu2.e[x][0]] = 1;
            used[x] = 1;
        }
        x = dsu1.get(i);
        if(dsu1.e[x].size() < 2){continue;}
        if(!vis[x]){
            for(j = 0;j < dsu1.e[x].size() - 1; j++){
//                cout << dsu1.e[x][j] << ' ';
                ans[dsu1.e[x][j]][dsu1.e[x][j + 1]] = 1;
                ans[dsu1.e[x][j + 1]][dsu1.e[x][j]] = 1;
            }
//            cout << dsu1.e[x][j] << endl;
            vis[x] = 1;
        }
    }

    build(ans);
    return 1;
}
/*
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:102:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for(j = 0;j < dsu2.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:113:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(j = 0;j < dsu1.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~

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