Submission #821556

#	Time	Username	Problem	Language	Result	Execution time	Memory
821556		caganyanmaz	Parachute rings (IOI12_rings)	C++17	20 / 100	773 ms	133896 KiB

rings

#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;




void __print(int i) { cerr << i; }
void __print(bool i) { cerr << (i ? "true" : "false"); }

template<typename T>
void __print(T& t) { cerr << "{"; int f = 0; for (auto& i : t) { cerr << (f++ ? ", " : ""); __print(i); } cerr << "}"; }

void _print() { cerr << "]\n"; }

template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }

#ifdef DEBUGGING
#define debug(x...) cerr <<"[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...) 42
#endif

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 = 1e6;
int n;

vector<int> p;
vector<int> g[MXN];
Node node[MXN];
bitset<MXN> in_loop;
vector<int> touching_loop;


void merge(int a, int b);

void Init(int N_)
{
        n = N_;
        for (int i = 0; i < n; i++)
        {
                node[i] = Node(i);
                p.pb(i);
        }


}

void check(int node)
{
        if (g[node].size() <= 2 || g[node].size() >= 5)
                return;
        vector<int> p_new;
        if (g[node].size() == 3)
                for (int i : p)
                        if (i == node || find(g[node].begin(), g[node].end(), i) != g[node].end())
                                p_new.pb(i);
        if (g[node].size() == 4)
                for (int i : p)
                        if (i == node)
                                p_new.pb(i);
        sort(p_new.begin(), p_new.end());
        p = p_new;

}

vector<int> current_a;
int visited[MXN];
bool visited_loop = false;
int counter = 0;
int lll = 1;

bool dfs(int node, int target)
{
        if (in_loop[node] || (node == target && !visited_loop))
        {
                current_a.pb(node);
                in_loop[node] = true;
                return true;
        }
        if (node == target)
        {
                in_loop[node] = true;
                return true;
        }
        bool valid = false;
        visited[node] = lll;
        for (int c : g[node])
        {
                if (visited[c] != lll && dfs(c, target))
                {
                        debug(node, c);
                        valid = true;
                }
        }
        if (valid && !visited_loop)
                current_a.pb(node);
        if (valid)
                in_loop[node] = true;
        return valid;
}

void check(int a, int b)
{
        current_a.clear();
        if (!in_loop[a] && !in_loop[b])
        {
                dfs(a, b);
                if (visited_loop)
                {
                        dfs(b, a);
                        assert(current_a.size() <= 2);
                        if (current_a.size() <= 1)
                                current_a.clear();
                        if (current_a[0] == current_a[1])
                                current_a.pop_back();
                }
        }
        else if (in_loop[a] && in_loop[b])
        {
                current_a.pb(a);
                current_a.pb(b);
        }
        else  // One in loop, one out loop
        {
                if (!in_loop[a]) swap(a, b);
                debug(b, a, (bool)in_loop[0]);
                dfs(b, a);
                debug(current_a);
        }

        sort(current_a.begin(), current_a.end());
        debug(current_a);
        int i = 0, j = 0;
        vector<int> new_p;
        while (i < current_a.size() && j < p.size())
        {
                if (current_a[i] == p[j])
                {
                        new_p.pb(current_a[i++]);
                        j++;
                }
                else if (current_a[i] > p[j])
                {
                        j++;
                }
                else
                {
                        i++;
                }
        }
        p = new_p;
        lll++;
        visited_loop = true;

}

void Link(int a, int b)
{
        debug(a, b);
        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);
}

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

}

void merge(int a, int b)
{
        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;
}

Compilation message (stderr)

rings.cpp: In function 'bool dfs(int, int)':
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:103:25: note: in expansion of macro 'debug'
  103 |                         debug(node, c);
      |                         ^~~~~
rings.cpp: In function 'void check(int, int)':
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:138:17: note: in expansion of macro 'debug'
  138 |                 debug(b, a, (bool)in_loop[0]);
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:140:17: note: in expansion of macro 'debug'
  140 |                 debug(current_a);
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:144:9: note: in expansion of macro 'debug'
  144 |         debug(current_a);
      |         ^~~~~
rings.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while (i < current_a.size() && j < p.size())
      |                ~~^~~~~~~~~~~~~~~~~~
rings.cpp:147:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while (i < current_a.size() && j < p.size())
      |                                        ~~^~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:171:9: note: in expansion of macro 'debug'
  171 |         debug(a, b);
      |         ^~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:184:9: note: in expansion of macro 'debug'
  184 |         debug(p);
      |         ^~~~~

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