Submission #821690

#	Time	Username	Problem	Language	Result	Execution time	Memory
821690		caganyanmaz	Parachute rings (IOI12_rings)	C++17	37 / 100	1975 ms	221856 KiB

rings

#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;
struct Node
{
        int head;
        int tail;
        int size;
        int nxt;
        Node(int i) : head(i), tail(i), size(1), nxt(-1) {}
        Node() : Node(-1) {}
};

constexpr static int MXN = 2e6;
int n;

set<int> p;
vector<int> g[MXN];
Node node[MXN];
bitset<MXN> in_loop;
int pred[MXN];
void merge(int a, int b);
void Init(int N_)
{
        n = N_;
        for (int i = 0; i < n; i++)
        {
                node[i] = Node(i);
                p.insert(i);
        }
        for (int i = 0; i < n; i++)
                pred[i] = -1;
}

void check(int node)
{
 		assert(node != -1);
        if (g[node].size() <= 2 || g[node].size() >= 5)
                return;
        set<int> p_new;
        if (g[node].size() == 3)
                for (int c : g[node])
                        if (p.find(c) != p.end())
                                p_new.insert(c);
        if (p.find(node) != p.end())
                p_new.insert(node);
        p.clear();
        p.insert(p_new.begin(), p_new.end());
}
set<int> current_a;
bitset<MXN> visited;
bool visited_loop = false;
bool dfs(int node, int target)
{
        visited[node] = true;
        if (node == target)
        {
                current_a.insert(node);
                in_loop[node] = true;
                return true;
        }
        bool valid = false;
        for (int c : g[node])
                if (!visited[c] && dfs(c, target))
                        valid = true;
        if (valid)
        {
                current_a.insert(node);
                in_loop[node] = true;
        }
        return valid;
}
void assign_pred(int node, int pp)
{
        pred[node] = pp;
        visited[node] = true;
        for (int c : g[node])
                if (!visited[node])
                        assign_pred(c, node);
}
void check(int a, int b)
{
        current_a.clear();
        if (!visited_loop)
        {
                dfs(a, b);
                visited.reset();
                assign_pred(a, -1);
        }
        else if (in_loop[a] && in_loop[b])
        {
                current_a.insert(a);
                current_a.insert(b);
        }
        else if(!in_loop[a] && !in_loop[b])
        {
                int i = a;
                for (; i != -1 && i != b && !in_loop[i]; i = pred[i])
                        in_loop[i] = true;
                if (i == b)
                {
                        p.clear();
                        return;
                }
                if (i != -1)
                        current_a.insert(i);
                int j = b;
                for (; j != -1 && j != a && !in_loop[j]; j = pred[j])
                        in_loop[j] = true;
                if (j == a)
                {
                        p.clear();
                        return;
                }
                if (j != -1)
                        current_a.insert(j);
        }
        else
        {
                if (in_loop[b]) swap(a, b);
          		assert(in_loop[a] && !in_loop[b]);
                assert(b != -1);
                for (; !in_loop[b]; b = pred[b])
                {
                        assert(b != -1); 
                  		in_loop[b] = true;
                }
                current_a.insert(b);
                current_a.insert(a);
        }
        for (auto it = current_a.begin(); it != current_a.end();)
        {
          		if (p.find(*it) == p.end())
                        current_a.erase(it++);
  				else
                  it++;
        }
        p.clear();
        p.insert(current_a.begin(), current_a.end());
        visited_loop = true;
}
void Link(int a, int b)
{
        if (p.empty())
                return;
        g[a].pb(b);
        g[b].pb(a);
        check(a);
        check(b);
        if (node[a].head == node[b].head)
        {
                check(a, b);
        }
        else
        {
                merge(node[a].head, node[b].head);
                auto ddfs = [&] (int node, int pp) -> void
                {
                        pred[node] = pp;
                        for (int c : g[node])
                                if (pred[c] == -1 && !in_loop[c])
                                        dfs(c, node);
                };
                if (in_loop[a] || pred[a] != -1)
                        ddfs(b, a);
                else if (in_loop[b] || pred[b] != -1)
                        ddfs(a, b);
        }
}

int CountCritical()
{
        return p.size();

}
void merge(int a, int b)
{
        assert(b != -1 && a != -1);
        if (node[a].size < node[b].size) swap(a, b);
        node[a].size += node[b].size;
        node[node[a].tail].nxt = b;
        node[a].tail = node[b].tail;
        for (;b != -1; b = node[b].nxt)
                node[b].head = a;
}

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