Submission #798195

#	Time	Username	Problem	Language	Result	Execution time	Memory
798195		HaroldVemeno	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	304 KiB

supertrees

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

using namespace std;
using ll = long long;

int n;
vector<vector<int>> am;
vector<vector<int>> res;
vector<int> comp;
int compn = 0;
vector<int> tv;
int tvn = 0;

int construct(vector<vector<int>> p) {
	n = p.size();
    am = std::move(p);
    comp.resize(n, -1);
    res.resize(n, vector<int>(n, 0));
    tv.resize(n, -1);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(am[i][j] == 3) {
                return 0;
            }
            if(am[i][j] != am[j][i]) {
                return 0;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        if(am[i][i] != 1) return 0;
        res[i][i] = 1;
    }
    vector<vector<int>> comps;
    for(int i = 0; i < n; ++i) {
        if(comp[i] != -1) continue;
        comp[i] = compn++;
        comps.push_back({});
        for(int j = 0; j < n; ++j) {
            if(am[i][j] > 0) {
                comp[j] = comp[i];
                comps[comp[i]].push_back(j);
            }
        }
    }
    for(auto& c : comps) {
        for(auto a : c) {
            for(auto b : c) {
                if(am[a][b] == 0) return 0;
            }
        }
    }
    vector<vector<int>> tvbycomps(compn);
    vector<vector<int>> ts;
    for(int i = 0; i < n; ++i) {
        if(tv[i] != -1) continue;
        tv[i] = tvn++;
        ts.push_back({});
        tvbycomps[comp[i]].push_back(i);
        for(int j = 0; j < n; ++j) {
            if(am[i][j] == 1) {
                tv[j] = tv[i];
                res[i][j] = 1;
                res[j][i] = 1;
                ts[tv[i]].push_back(j);
            }
        }
    }
    for(auto& c : ts) {
        for(auto a : c) {
            for(auto b : c) {
                if(am[a][b] != 1) return 0;
            }
        }
    }
    for(auto& cts : tvbycomps) {
        for(int i = 0; i < cts.size(); ++i) {
            for(int j = i+1; j < cts.size(); ++j) {
                for(auto a : ts[cts[i]]) {
                    for(auto b : ts[cts[j]]) {
                        if(am[a][b] != 2) return 0;
                    }
                }
            }
        }
    }
    for(auto& cts : tvbycomps) {
        if(cts.size() == 1) continue;
        if(cts.size() == 2) return 0;
        for(int i = 0; i < cts.size()-1; ++i) {
            res[cts[i]][cts[i+1]] = 1;
            res[cts[i+1]][cts[i]] = 1;
        }
        res[cts[0]][cts.back()] = 1;
        res[cts.back()][cts[0]] = 1;
    }

    build(res);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i = 0; i < cts.size(); ++i) {
      |                        ~~^~~~~~~~~~~~
supertrees.cpp:79:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j = i+1; j < cts.size(); ++j) {
      |                              ~~^~~~~~~~~~~~
supertrees.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i = 0; i < cts.size()-1; ++i) {
      |                        ~~^~~~~~~~~~~~~~

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