Submission #302949

#	Time	Username	Problem	Language	Result	Execution time	Memory
302949		ivan24	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	309 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(2,vi());
        vi hasCurSet(n,0);
        for (auto j: cur_set){
            if (hasCurSet[j]) continue;
            hasCurSet[j] = true;

            bool hasOne = false;
            for (auto k: cur_set){
                if (k != j && p[j][k] == 1) hasOne = true;
            }
            if (hasOne){
                ll cur_one = 0;
                for (ll k = 0; 2 > k; k++){
                    if (one_set[k].size()) cur_one++;
                }
                if (cur_one == 2) return 0;
                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] = true;
                    }
                }
            }else{
                two_set.push_back(j);
            }
        }

        /*
        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;
        */

        vi nodes = concat(one_set[0],two_set,one_set[1]);
        for (ll j = 0; nodes.size() > j+1; j++){
            add_edge(nodes[j],nodes[j+1]);
            //cout << nodes[j] << " " << nodes[j+1] << endl;
        }
        if (two_set.size()){
            ii extra_edge = ii(two_set[0],two_set[two_set.size()-1]);
            if (one_set[0].size()) extra_edge.F = one_set[0][0];
            if (one_set[1].size()) extra_edge.S = one_set[1][0];
            bool b = add_edge(extra_edge.F, extra_edge.S);
            //cout << extra_edge.F << " " << extra_edge.S << endl;
            if (!b) return 0;
        }

        bool b = checkOnes(one_set[0]) && checkOnes(one_set[1]);
        b = b && checkTwos(two_set,one_set[0]) && checkTwos(two_set,one_set[1]);
        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;
            }
            bool res = processGroup(cur_set);
        }
        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:104:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  104 |         for (ll j = 0; nodes.size() > j+1; j++){
      |                        ~~~~~~~~~~~~~^~~~~
supertrees.cpp: In member function 'bool Solver::solve()':
supertrees.cpp:153:18: warning: unused variable 'res' [-Wunused-variable]
  153 |             bool res = processGroup(cur_set);
      |                  ^~~

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