oj.uz

Submission #779199

# Submission time Handle Problem Language Result Execution time Memory
779199 2023-07-11T08:55:08 Z kamelfanger83 Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 212 KB 
#include "supertrees.h"
#include <vector>
#include <cassert>
#include <numeric>

using namespace std;

template <typename T>
bool operator==(vector<T> &a, vector<T> &b){
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

template <typename T>
bool operator!=(vector<T> &a, vector<T> &b){
    return !(a==b);
}

struct Unionfind {
    vector<int> group;
    Unionfind(int n) {
        group.resize(n);
        iota(group.begin(), group.end(), 0);
    }
    int find(int i){
        if (group[i] == i) return i;
        return group[i] = find(group[i]);
    }
    void merge(int a, int b){
        a = find(a); b = find(b);
        if (a == b) return;
        group[b] = group[a];
    }
};

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

    Unionfind unionfind (n);

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] != 0) unionfind.merge(i, j);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if ((p[i][j] == 0) && (unionfind.find(i) == unionfind.find(j))) return 0;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!res[i].empty()) continue;
        res[i].assign(n, 0);
        inc[i] = true;
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 0 || i == j) continue;
            if (p[i][j] == 1){
                if (p[i] != p[j]) return 0;
                res[j].assign(n, 0);
                res[j][i] = 1;
                res[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!inc[i]) continue;
        int ft = -1, lt = -1, bt = -1, at = -1;
        for (int j = 0; j < n; ++j) {
            if (inc[j]){
                if (p[i][j] != 2) return 0;
                if (ft == -1) ft = j;
                if (j < i) bt = j;
                if (j > i && at == -1) at = j;
                lt = j;
            }
        }
        if (lt == -1) continue;
        if (at == -1) at = ft;
        if (bt == -1) bt = lt;
        res[i][bt] = 1;
        res[i][at] = 1;
    }

    build(res);
    return 1;
}

Compilation message

supertrees.cpp: In instantiation of 'bool operator==(std::vector<T>&, std::vector<T>&) [with T = int]':
supertrees.cpp:18:15:   required from 'bool operator!=(std::vector<T>&, std::vector<T>&) [with T = int]'
supertrees.cpp:64:32:   required from here
supertrees.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -