Submission #798206

#	Time	Username	Problem	Language	Result	Execution time	Memory
798206		HaroldVemeno	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	186 ms	23616 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({i});
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            if(am[i][j] > 0) {
                comp[j] = comp[i];
                comps[comp[i]].push_back(j);
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if((comp[i] == comp[j]) != (am[i][j] > 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({i});
        tvbycomps[comp[i]].push_back(i);
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            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 : comps) {
        for(int a : c) {
            for(int b : c) {
                if((tv[a] == tv[b]) != (am[a][b] == 1)) {
                    return 0;
                }
                if((tv[a] != tv[b]) != (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;
    }

    for(int i = 0; i < n; ++i) {
        res[i][i] = 0;
    }
    build(res);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = 0; i < cts.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