제출 #557562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557562		timreizin	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	3129 ms	121660 KiB

rings

#include <vector>
#include <numeric>
#include <array>
#include <algorithm>

using namespace std;

struct DSU
{
    int n, comps;
    vector<int> parent, size;
    vector<int> adj;
    array<int, 5> counter;
    int res, v;

    DSU(int n = 0, int v = -1) : n(n), v(v)
    {
        parent.resize(n);
        size.resize(n, 1);
        iota(parent.begin(), parent.end(), 0);
        comps = n;
        adj.resize(n);
        counter.fill(0);
        counter[0] = n;
        res = (v == -1 ? n : 1);
    }

    int getParent(int i)
    {
        if (parent[i] == i) return i;
        return parent[i] = getParent(parent[i]);
    }

    void unite(int a, int b)
    {
        if (res == 0) return;
        if (a == v || b == v) return;
        int wasCyc = comps - counter[0] - counter[1] / 2;
        --counter[min(adj[a], 4)];
        --counter[min(adj[b], 4)];
        ++adj[a];
        ++adj[b];
        ++counter[min(adj[a], 4)];
        ++counter[min(adj[b], 4)];
        if (counter[3] + counter[4] > 0)
        {
            res = 0;
            return;
        }
        a = getParent(a);
        b = getParent(b);
        if (a != b) --comps;
        int newCyc = comps - counter[0] - counter[1] / 2;
        if (v != -1 && newCyc > 0)
        {
            res = 0;
            return;
        }
        else if (v == -1)
        {
            if (newCyc >= 2)
            {
                res = 0;
                return;
            }
            if (newCyc == 1 && wasCyc == 0)
            {
                vector<int> cnt(n);
                for (int i = 0; i < n; ++i)
                {
                    if (adj[i] < 2) cnt[getParent(i)] = -1e9;
                    else ++cnt[getParent(i)];
                }
                res = 0;
                for (int i = 0; i < n; ++i) res = max(res, cnt[i]);
            }
        }
        if (a != b)
        {
            if (size[a] < size[b]) swap(a, b);
            size[a] += size[b];
            parent[b] = a;
        }
    }

};

int n;
vector<vector<int>> adj;
array<DSU, 8> dsu;
array<int, 5> counter;
vector<int> curs, dop;
vector<pair<int, int>> edges;

void Init(int N_)
{
    n = N_;
    adj.resize(n);
    dsu[0] = DSU(n);
    counter[0] = n;
    curs.push_back(-1);
}

void Link(int a, int b)
{
    int was3 = counter[3], was4 = counter[4];
    --counter[min((int)adj[a].size(), 4)];
    --counter[min((int)adj[b].size(), 4)];
    adj[a].push_back(b);
    adj[b].push_back(a);
    ++counter[min((int)adj[a].size(), 4)];
    ++counter[min((int)adj[b].size(), 4)];
    if (counter[4] > 1) return;
    if (counter[4] > was4)
    {
        curs.clear();
        dop.clear();
        for (int i = 0; i < 7; ++i) dsu[i].res = 0;
        if (adj[a].size() == 4) curs.push_back(a);
        if (adj[b].size() == 4) curs.push_back(b);
        dsu[0] = DSU(n, curs[0]);
        for (auto [a, b] : edges) dsu[0].unite(a, b);
    }
    else if (counter[3] > was3)
    {
        if (counter[3] > 4 && was3 <= 4)
        {
            curs.clear();
            dop.clear();
            for (int i = 0; i < 7; ++i) dsu[i].res = 0;
        }
        if (counter[3] <= 4)
        {
            if (was3 == 0) curs.clear();
            if (adj[a].size() == 3) curs.push_back(a);
            if (adj[b].size() == 3) curs.push_back(b);
            for (int i = 0; i < 7; ++i) dsu[i].res = 0;
            dop.clear();
            for (int i = 0; i < curs.size(); ++i)
            {
                dsu[i] = DSU(n, curs[i]);
                for (auto [a, b]: edges) dsu[i].unite(a, b);
            }
            //calc dop
            if (curs.size() < 3)
            {
                for (int i = 0; i < n; ++i)
                {
                    if (adj[i].size() < 3)
                    {
                        bool was0 = false, was1 = curs.size() == 1;
                        for (int j: adj[i])
                        {
                            was0 = was0 || (j == curs[0]);
                            if (curs.size() == 2) was1 = was0 || (j == curs[1]);
                        }
                        if (was0 && was1)
                        {
                            dop.push_back(i);
                        }
                    }
                }
            }
            for (int i = 0; i < dop.size(); ++i)
            {
                dsu[i + curs.size()] = DSU(n, dop[i]);
                for (auto [a, b]: edges) dsu[i + curs.size()].unite(a, b);
            }
        }
    }
    for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
    for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
    edges.emplace_back(a, b);
}

int CountCritical()
{
    if (counter[4] > 1) return 0;
    int res = 0;
    for (int i = 0; i < 8; ++i) res += dsu[i].res;
    return res;
}

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

rings.cpp: In function 'void Link(int, int)':
rings.cpp:139:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for (int i = 0; i < curs.size(); ++i)
      |                             ~~^~~~~~~~~~~~~
rings.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for (int i = 0; i < dop.size(); ++i)
      |                             ~~^~~~~~~~~~~~
rings.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
      |                     ~~^~~~~~~~~~~~~
rings.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31