oj.uz

Submission #1071280

# Submission time Handle Problem Language Result Execution time Memory
1071280 2024-08-23T06:32:22 Z Ignut Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 0 ms 348 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void build(vector<vector<int>> b);

struct DSU {
    vector<int> p;
    vector<vector<int>> comp;
    void Init(int n) {
        p.clear(), comp.clear();
        for (int i = 0; i < n; i ++) p.push_back(i), comp.push_back({i});
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    void Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return;
        if (comp[u].size() > comp[v].size()) swap(u, v);
        p[u] = v;
        for (int val : comp[u]) comp[v].push_back(val);
    }
};

int construct(vector<vector<int>> p) {
    int n = p.size();
    DSU dsu; dsu.Init(n);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (p[i][j] == 2) {
                dsu.Unite(i, j);
            }
        }
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            bool f1 = (p[i][j] == 2);
            bool f2 = (dsu.Get(i) == dsu.Get(j));
            if (f1 != f2)
                return 0;
        }
    }
    vector<vector<int>> b(n);
    for (int i = 0; i < n; i ++) b[i].assign(n, 0);
    for (int i = 0; i < n; i ++) {
        if (dsu.Get(i) != i) continue;
        if (dsu.comp[i].size() <= 2)
            return 0;
        // cerr << dsu.comp[i].size() << '\n';
        for (int j = 0; j < dsu.comp[i].size(); j ++) {
            int u = dsu.comp[i][j], v = dsu.comp[i][(j + 1) % dsu.comp[i].size()];
            b[u][v] = b[v][u] = 1;
        }
    }
    build(b);
    return 1;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 344 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 0 ms 344 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 348 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 344 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 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -