oj.uz

Submission #557571

# Submission time Handle Problem Language Result Execution time Memory
557571 2022-05-05T13:31:11 Z timreizin Parachute rings (IOI12_rings) C++17
0 / 100
 2388 ms 154516 KB 
#include <vector>
#include <numeric>
#include <array>
#include <algorithm>
#include <set>
#include <iostream>

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 < 8; ++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 && counter[4] == 0)
    {
        if (counter[3] > 4 && was3 <= 4)
        {
            curs.clear();
            dop.clear();
            for (int i = 0; i < 8; ++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 < 8; ++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);
            }
            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 = was1 || (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;
    vector<int> th, fo;
    for (int i = 0; i < n; ++i)
    {
        if (adj[i].size() == 3) th.push_back(i);
        else if (adj[i].size() >= 4)  fo.push_back(i);
    }
    if (res == 0)
    {
        vector<int> help = adj[fo.front()];
        set<int> help2(help.begin(), help.end());
        vector<int> mfs;
        for (int i : th)
        {
            if (help2.find(i) == help2.end())
            {
                mfs.push_back(i);
            }
        }
        int a = 4;
    }
    return res;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:141:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for (int i = 0; i < curs.size(); ++i)
      |                             ~~^~~~~~~~~~~~~
rings.cpp:165:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for (int i = 0; i < dop.size(); ++i)
      |                             ~~^~~~~~~~~~~~
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 < curs.size(); ++i) dsu[i].unite(a, b);
      |                     ~~^~~~~~~~~~~~~
rings.cpp:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
      |                     ~~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:200:13: warning: unused variable 'a' [-Wunused-variable]
  200 |         int a = 4;
      |             ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Runtime error 3 ms 1236 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 38984 KB Output is correct
2 Correct 1109 ms 87920 KB Output is correct
3 Correct 669 ms 98148 KB Output is correct
4 Correct 1127 ms 78448 KB Output is correct
5 Correct 1062 ms 78500 KB Output is correct
6 Correct 1053 ms 77052 KB Output is correct
7 Correct 644 ms 97728 KB Output is correct
8 Correct 1897 ms 111876 KB Output is correct
9 Correct 2388 ms 121368 KB Output is correct
10 Runtime error 743 ms 154516 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Runtime error 3 ms 1236 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Runtime error 3 ms 1236 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Runtime error 3 ms 1236 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -