Submission #557484

#	Time	Username	Problem	Language	Result	Execution time	Memory
557484		timreizin	Parachute rings (IOI12_rings)	C++17	0 / 100	1792 ms	262144 KiB

rings

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

using namespace std;

struct DSU
{
    int n, comps;
    vector<int> parent, size;
    vector<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;
        --counter[adj[a].size()];
        --counter[adj[b].size()];
        adj[a].push_back(b);
        adj[b].push_back(a);
        ++counter[adj[a].size()];
        ++counter[adj[b].size()];
        a = getParent(a);
        b = getParent(b);
        if (a == b)
        {
            res = 0;
            return;
        }
        if (counter[3] + counter[4] > 0)
        {
            res = 0;
            return;
        }
        --comps;
        if (size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        parent[b] = a;
    }

};

int n;
vector<vector<int>> adj;
array<DSU, 4> 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[adj[a].size()];
    --counter[adj[b].size()];
    adj[a].push_back(b);
    adj[b].push_back(a);
    ++counter[adj[a].size()];
    ++counter[adj[b].size()];
    if (counter[4] > 1 || counter[3] > 4) 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 (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 || counter[3] > 4) return 0;
    int res = 0;
    for (int i = 0; i < 7; ++i) res += dsu[i].res;
    return res;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int i = 0; i < curs.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
rings.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int i = 0; i < dop.size(); ++i)
      |                         ~~^~~~~~~~~~~~
rings.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
      |                     ~~^~~~~~~~~~~~~
rings.cpp:139:23: 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 < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
      |                     ~~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:147:47: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
  147 |     for (int i = 0; i < 7; ++i) res += dsu[i].res;
rings.cpp:147:23: note: within this loop
  147 |     for (int i = 0; i < 7; ++i) res += dsu[i].res;
      |                     ~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:105:48: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
  105 |         for (int i = 0; i < 7; ++i) dsu[i].res = 0;
rings.cpp:105:27: note: within this loop
  105 |         for (int i = 0; i < 7; ++i) dsu[i].res = 0;
      |                         ~~^~~
rings.cpp:94:48: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
   94 |         for (int i = 0; i < 7; ++i) dsu[i].res = 0;
rings.cpp:94:27: note: within this loop
   94 |         for (int i = 0; i < 7; ++i) dsu[i].res = 0;
      |                         ~~^~~

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