Submission #313781

#	Time	Username	Problem	Language	Result	Execution time	Memory
313781		nikatamliani	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	316 ms	22360 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#include "supertrees.h"
int find_set(int x, vector < int > &parent) {
    return parent[x] == x ? x : parent[x] = find_set(parent[x], parent);
}
void union_sets(int x, int y, vector < int > &parent) {
    x = find_set(x, parent);
    y = find_set(y, parent);
    parent[x] = y; 
}
int construct(vector < vector < int > > p) {
    int n = p.size();
    vector < int > parent(n);
    for(int i = 0; i < n; ++i) parent[i] = i;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(p[i][j] == 3) return 0;
            if(p[i][j] > 0) {
                union_sets(i, j, parent);
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(find_set(i, parent) == find_set(j, parent) && !p[i][j]) {
                return 0;
            }
        }
    }
    vector < vector < int > > g(n, vector < int >(0, 0));
    for(int i = 0; i < n; ++i) {
        g[find_set(i, parent)].push_back(i);
    }
    for(int i = 0; i < n; ++i) parent[i] = i;
    vector < vector < int > > edges(n, vector < int >(n, 0));
    for(int i = 0; i < n; ++i) {
        if(g[i].empty()) continue;
        for(int x : g[i]) {
            for(int y : g[i]) {
                if(p[x][y] == 1) {
                    union_sets(x, y, parent);
                }
            }
        }
        for(int x : g[i]) {
            for(int y : g[i]) {
                if(find_set(x, parent) == find_set(y, parent) && p[x][y] == 2) {
                    return 0;
                }
            }
        }
        vector < int > last(n, -1), parents;
        for(int x : g[i]) {
            int pp = find_set(x, parent);
            if(~last[pp]) {
                edges[last[pp]][x] = edges[x][last[pp]] = 1; 
            }
            last[pp] = x;
            if(x == pp) {
                parents.push_back(x);
            }
        }
        if(parents.size() == 2) {
            return 0;
        }
        for(int j = 1; j < parents.size(); ++j) {
            int from = parents[j - 1], to = parents[j];
            edges[from][to] = edges[to][from] = 1; 
        }
        int from = parents.back(), to = parents[0];
        if(from != to) {
            edges[from][to] = edges[to][from] = 1;  
        }
    }
    build(edges);
    return 1;
}

Compilation message (stderr)

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

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