제출 #1061865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061865		vjudge1	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	147 ms	22212 KiB

supertrees

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

using namespace std;

using vi = vector<int>;

struct DSU {
    vi e;
    DSU(int n) : e(n, -1) {}

    int repr(int u) {
        int u0 = u;
        while(e[u] >= 0) u = e[u];
        while(e[u0] >= 0) {
            int v = e[u0];
            e[u0] = u;
            u0 = v;
        }
        return u;
    }

    void join(int u, int v) {
        u = repr(u); v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }

    bool same(int u, int v) { return repr(u) == repr(v); }

    vector<vi> comp() {
        ///va da componentele
        int n = int(e.size()), nr = 0;
        map<int, int> Id;
        for(int i = 0; i < n; ++i) {
            if(e[i] < 0) {
                Id[i] = nr++;
            }
        }
        vector<vi> Re(nr);
        for(int i = 0; i < n; ++i)
            Re[Id[repr(i)]].push_back(i);
        return Re;
    }
};

bool solve(vi comp, vector<vi> &p, vector<vi> &L) {
    int m = (int)comp.size(), n = (int)p.size();
    DSU Sol(m);
    bool ok = true;
    for(int i = 0; i < m; ++i)
        for(int j = i + 1; j < m; ++j)
            if(p[comp[i]][comp[j]] == 0 || p[comp[i]][comp[j]] == 3) ok = 0;
    for(int i = 0; i < m; ++i)
        for(int j = i + 1; j < m; ++j)
            if(p[comp[i]][comp[j]] == 1) Sol.join(i, j); /// arborescenta
    for(int i = 0; i < m; ++i)
        for(int j = i + 1; j < m; ++j)
            if(p[comp[i]][comp[j]] != 1 && Sol.same(i, j)) ok = false;
    auto Arb = Sol.comp();
    vi A;
    for(auto sir : Arb) {
        for(int i = 1; i < (int)sir.size(); ++i) {
            L[comp[sir[0]]][comp[sir[i]]] = 1;
            L[comp[sir[i]]][comp[sir[0]]] = 1;
        }
        A.push_back(comp[sir[0]]);
    }
    for(int i = 0; i + 1 < (int)A.size(); ++i) {
        L[A[i]][A[i + 1]] = 1;
        L[A[i + 1]][A[i]] = 1;
    }
    if(A.size() != 1) {
        L[A[0]][A.back()] = 1;
        L[A.back()][A[0]] = 1;
    }
    return ok;
}

int construct(vector<vi> p) {
    int n = int(p.size());
    DSU Sol(n);
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            if(p[i][j]) Sol.join(i, j);
        }
    }
    bool ok = true;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            if(p[i][j] == 0 && Sol.same(i, j))
                ok = false;
            if(p[i][j] == 3)
                ok = false;
        }
    }
    if(!ok) return 0;
    auto C = Sol.comp();
    vector<vi> Muchii(n, vi(n, 0));
    for(auto comp : C) {
        ok &= solve(comp, p, Muchii);
    }
    if(ok) {
        build(Muchii);
    }
    return ok;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'bool solve(vi, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
supertrees.cpp:50:31: warning: unused variable 'n' [-Wunused-variable]
   50 |     int m = (int)comp.size(), n = (int)p.size();
      |                               ^

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