Submission #302991

#	Time	Username	Problem	Language	Result	Execution time	Memory
302991		ivan24	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	264 ms	26232 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

void build(vvi b);

class Solver{
private:
    vvi p;
    ll n;
    vvi ans;
    vi hasSet;
    bool add_edge(ll u, ll v){
        if (ans[u][v] || u == v) return 0;
        ans[u][v] = ans[v][u] = 1;
        return 1;
    }
    vi concat(const vi& v1, const vi& v2, const vi& v3){
        vi res;
        for (ll i = v1.size()-1; i >= 0; i--) res.push_back(v1[i]);
        for (auto i: v2) res.push_back(i);
        for (auto i: v3) res.push_back(i);
        return res;
    }

    bool checkOnes(const vi& v){
        for (auto i: v){
            for (auto j: v){
                if (j != i && p[i][j] != 1) return 0;
            }
        }
        return 1;
    }
    bool checkTwos(const vi& two, const vi& one){
        for (auto i: two){
            for (auto j: one){
                if (p[i][j] != 2) return 0;
            }
            for (auto j: two){
                if (p[i][j] != 2 && i != j) return 0;
            }
        }
        return 1;
    }


    bool processGroup(const vi& cur_set){
        // check if all are connected to each other
        for (auto j: cur_set){
            for (auto k: cur_set){
                if (p[j][k] == 0 && j != k) return 0;
            }
        }
        vi two_set; vvi one_set;
        vi hasCurSet(n,0);
        for (auto j: cur_set){
            if (hasCurSet[j]) continue;
            hasCurSet[j] = 2;

            for (auto k: cur_set){
                if (k != j && p[j][k] == 1) hasCurSet[j] = 1;
            }
            if (hasCurSet[j] == 1){
                ll cur_one = one_set.size();
                one_set.push_back(vi());
                one_set[cur_one].push_back(j);
                for (auto k: cur_set){
                    if (p[j][k] == 1 && j != k){
                        one_set[cur_one].push_back(k);
                        if (hasCurSet[k]) return 0;
                        hasCurSet[k] = 1;
                    }
                }
            }else{
                two_set.push_back(j);
                hasCurSet[j] = 2;
            }
        }

        /*
        cout << "one_set:\n";
        for (auto j: one_set){
            for (auto k: j) cout << k << " ";
            cout << endl;
        }
        cout << "two_set:\n";
        for (auto j: two_set) cout << j << " ";
        cout << endl;
        */
        if (one_set.size() == 1 && two_set.size() == 0){
            for (ll i = 0; one_set[0].size() > i+1; i++){
                add_edge(one_set[0][i],one_set[0][i+1]);
            }
        }else{
            if (two_set.size() < one_set.size()) return 0;
            for (auto i: one_set){
                for (auto j: i){
                    for (auto k: i){
                        if (k == j) continue;
                        if (p[j][k] != 1) return 0;
                    }
                }
                for (ll j = 0; i.size() > j+1; j++){
                    add_edge(i[j],i[j+1]);
                }
            }
            for (ll i = 0; two_set.size() > i; i++){
                if (i) add_edge(two_set[i],two_set[i-1]);
                if (one_set.size() > i) add_edge(one_set[i][0],two_set[i]);
            }
        }
        if (two_set.size()){
            ii extra_edge = ii(two_set[0],two_set[two_set.size()-1]);
            if (one_set.size() > 0) extra_edge.F = one_set[0][0];
            if (one_set.size() > two_set.size()-1) extra_edge.S = one_set[two_set.size()-1][0];
            bool b = add_edge(extra_edge.F, extra_edge.S);
            //cout << extra_edge.F << " " << extra_edge.S << endl;
            //if (!b) return 0;
        }

        for (auto i: cur_set){
            for (auto j: cur_set){
                if (j != i) p[i][j] = 0;
            }
        }

        return 1;
    }
public:
    Solver(vvi p): p(p),n(p.size()),ans(n,vi(n,0)), hasSet(n,0){

    }
    bool solve(){
        for (int i = 0; n > i; i++){
            if (hasSet[i]){
                for (ll j = 0; n > j; j++){
                    if (p[i][j] && j != i) return 0;
                }
                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;
                }
            }
            if (cur_set.size() > 1){
                bool res = processGroup(cur_set);
                if (!res) return 0;
            }
        }
        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;
    }
};

int construct(vvi p) {
    Solver mySolver(p);
    return mySolver.solve();
}

Compilation message (stderr)

supertrees.cpp: In member function 'bool Solver::processGroup(const vi&)':
supertrees.cpp:100:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  100 |             for (ll i = 0; one_set[0].size() > i+1; i++){
      |                            ~~~~~~~~~~~~~~~~~~^~~~~
supertrees.cpp:112:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  112 |                 for (ll j = 0; i.size() > j+1; j++){
      |                                ~~~~~~~~~^~~~~
supertrees.cpp:116:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  116 |             for (ll i = 0; two_set.size() > i; i++){
      |                            ~~~~~~~~~~~~~~~^~~
supertrees.cpp:118:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  118 |                 if (one_set.size() > i) add_edge(one_set[i][0],two_set[i]);
      |                     ~~~~~~~~~~~~~~~^~~
supertrees.cpp:125:18: warning: unused variable 'b' [-Wunused-variable]
  125 |             bool b = add_edge(extra_edge.F, extra_edge.S);
      |                  ^

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