Submission #395424

#	Time	Username	Problem	Language	Result	Execution time	Memory
395424		snasibov05	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	256 ms	24084 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define ll long long
#define double long double
#define ull unsigned long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define s second
#define f first
#define pb push_back
#define oo 1000000000000000000ll

int solve_cmp(vector<int>& cmp, vector<vector<int>>& p, vector<vector<int>>& ans){
    vector<vector<int>> tree;
    vector<int> tree_n(cmp.size(), -1);
    for (int i = 0; i < cmp.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (p[cmp[i]][cmp[j]] == 1){
                if (tree_n[i] != -1 && tree_n[i] != tree_n[j]) return 0;
                if (tree_n[i] != -1) continue;

                tree_n[i] = tree_n[j];
                tree[tree_n[i]].pb(i);
            }
        }
        if (tree_n[i] == -1) tree_n[i] = tree.size(), tree.pb({i});
    }

    if (tree.size() == 2) return 0;

    vector<int> rt;

    for (auto v : tree){
        vector<bool> cur(cmp.size());
        for (int i = 0; i < v.size(); ++i) {
            cur[v[i]] = true;
        }

        for (int i = 0; i < v.size(); ++i) {
            for (int j = 0; j < cmp.size(); ++j) {
                if (cur[j] && p[cmp[v[i]]][cmp[j]] != 1) return 0;
                if (!cur[j] && p[cmp[v[i]]][cmp[j]] != 2) return 0;
            }
        }

        for (int i = 1; i < v.size(); ++i) {
            ans[cmp[v[i]]][cmp[v[0]]] = ans[cmp[v[0]]][cmp[v[i]]] = 1;
        }

        rt.pb(v[0]);
    }

    for (int i = 0; i < rt.size() - 1; ++i) {
        ans[cmp[rt[i]]][cmp[rt[i+1]]] = ans[cmp[rt[i+1]]][cmp[rt[i]]] = 1;
    }

    if(rt.size() > 1) ans[cmp[rt.back()]][cmp[rt[0]]] = ans[cmp[rt[0]]][cmp[rt.back()]] = 1;


    return 1;
}

int construct(vector<vector<int>> p) {
    int n = p.size();

    vector<vector<int>> ans(n, vector<int>(n));
    vector<vector<int>> cmp;
    vector<int> cmp_n(n , -1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (p[i][j] == 3) return 0;
            if (p[i][j] > 0){
                if (cmp_n[i] != -1 && cmp_n[i] != cmp_n[j]) return 0;
                if (cmp_n[i] != -1) continue;

                cmp_n[i] = cmp_n[j];
                cmp[cmp_n[i]].pb(i);
            }
        }
        if (cmp_n[i] == -1) cmp_n[i] = cmp.size() , cmp.pb({i});
    }

    for (auto v : cmp){
        if (!solve_cmp(v, p, ans)) return 0;
    }



    build(ans);
    return 1;
}

/*

void solve() {

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tst; tst = 1;
    //cin >> tst;
    while (tst--){
        solve();
    }

    return 0;

}

 */

Compilation message (stderr)

supertrees.cpp: In function 'int solve_cmp(std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
supertrees.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < cmp.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
supertrees.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < v.size(); ++i) {
      |                         ~~^~~~~~~~~~
supertrees.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < v.size(); ++i) {
      |                         ~~^~~~~~~~~~
supertrees.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for (int j = 0; j < cmp.size(); ++j) {
      |                             ~~^~~~~~~~~~~~
supertrees.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 1; i < v.size(); ++i) {
      |                         ~~^~~~~~~~~~
supertrees.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < rt.size() - 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~

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