Submission #675730

#	Time	Username	Problem	Language	Result	Execution time	Memory
675730		YENGOYAN	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	237 ms	30280 KiB

supertrees

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

using namespace std;

vector<int> par, sizes;

int get(int u) {
    if (par[u] == u) return u;
    return par[u] = get(par[u]);
}

bool areInOne(int u, int v) {
    return get(u) == get(v);
}

void union_sets(int u, int v) {
    int a = get(u), b = get(v);
    if (a == b) return;
    if (sizes[a] < sizes[b]) swap(a, b);
    sizes[a] += sizes[b];
    par[b] = a;
}

vector<int> comp;

void dfs(int u, vector<vector<int>>& gp, vector<bool>& vis) {
    comp.push_back(u);
    vis[u] = 1;
    for (int& v : gp[u]) {
        if (!vis[v]) {
            dfs(v, gp, vis);
        }
    }
}

int construct(vector<vector<int>> p) {

    int n = p.size();
    vector<vector<int>> gp(n, vector<int>(n));
    par = sizes = vector<int>(n);
    for (int i = 0; i < n; i++) par[i] = i, sizes[i] = 1;
    set<int> vec;
    vector<vector<int>> gppppp(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] == 3) {
                gppppp[i].push_back(j);
                gppppp[j].push_back(i);
                union_sets(i, j);   
            } 
            if (areInOne(i, j) && p[i][j] != 3) {
                return 0;
            }
        }
    }
    vector<bool> mv(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] == 3) {
                if (!mv[i]) {
                    comp.clear();
                    dfs(i, gppppp, mv);
                    if (comp.size() < 4) return 0;
                    for (int i = 0; i < comp.size() - 1; ++i) gp[comp[i]][comp[i + 1]] = gp[comp[i + 1]][comp[i]] = 1;
                    gp[comp.back()][comp[0]] = gp[comp[0]][comp.back()] = 1;
                    gp[comp[0]][comp[2]] = gp[comp[2]][comp[0]];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!areInOne(i, j) && p[i][j] == 1) {
                gp[i][j] = gp[j][i] = 1;
                union_sets(i, j);
            }
        }
    }
    vector<bool> used(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 1) {
                used[i] = used[j] = 1;
                vec.insert(get(i));
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int u = get(i), v = get(j);
            if (u == v && !p[i][j]) return 0;
            if (u != v && p[i][j] == 1) return 0;
        }
    }
    vector<vector<int>> graph(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j]) {
                union_sets(i, j);
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int u = get(i), v = get(j);
            if (u == v && !p[i][j]) return 0;
            if (u != v && p[i][j]) return 0;
        }
    }

    vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        comp.clear();
        dfs(i, graph, vis);
        bool f = 0;
        vector<int> rightComp;
        int node = -1;
        for (int i = 0; i < comp.size(); i++) {
            if (!used[comp[i]]) rightComp.push_back(comp[i]);
            else if (vec.find(comp[i]) != vec.end()) rightComp.push_back(comp[i]);
        }
        for (int i = 0; i < rightComp.size() - 1; i++) {
            gp[rightComp[i]][rightComp[i + 1]] = gp[rightComp[i + 1]][rightComp[i]] = 1;
        }
        if (rightComp.size() > 2) gp[rightComp[0]][rightComp.back()] = gp[rightComp.back()][rightComp[0]] = 1;
        else if (rightComp.size() == 2) {
            return 0;
        }
    }
    /*
        1 1 2 2 2
        1 1 2 2 2
        2 2 1 1 2
        2 2 1 1 2
        2 2 2 2 1




    */
    build(gp);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                     for (int i = 0; i < comp.size() - 1; ++i) gp[comp[i]][comp[i + 1]] = gp[comp[i + 1]][comp[i]] = 1;
      |                                     ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < comp.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int i = 0; i < rightComp.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:119:14: warning: unused variable 'f' [-Wunused-variable]
  119 |         bool f = 0;
      |              ^
supertrees.cpp:121:13: warning: unused variable 'node' [-Wunused-variable]
  121 |         int node = -1;
      |             ^~~~

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