Submission #821486

#	Time	Username	Problem	Language	Result	Execution time	Memory
821486		caganyanmaz	Parachute rings (IOI12_rings)	C++17	0 / 100	4088 ms	69308 KiB

rings

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



void __print(int i) { cerr << i; }

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;


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;
bitset<MXN> visited;
int counter = 0;

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

void check(int a, int b)
{
        if (!in_loop[a] || !in_loop[b])
        {
                visited.reset();
                counter++;
                visited[a] = true;
                for (int i : g[a])
                        if (i != b)
                                dfs(i, b);
        }
        current_a.pb(a);
        current_a.pb(b);
        sort(current_a.begin(), current_a.begin());
        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;

}

void Link(int a, int 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:21:21: warning: statement has no effect [-Wunused-value]
   21 | #define debug(x...) 42
      |                     ^~
rings.cpp:89:25: note: in expansion of macro 'debug'
   89 |                         debug(node, c);
      |                         ^~~~~
rings.cpp: In function 'void check(int, int)':
rings.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         while (i < current_a.size() && j < p.size())
      |                ~~^~~~~~~~~~~~~~~~~~
rings.cpp:117:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         while (i < current_a.size() && j < p.size())
      |                                        ~~^~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:21:21: warning: statement has no effect [-Wunused-value]
   21 | #define debug(x...) 42
      |                     ^~
rings.cpp:151:9: note: in expansion of macro 'debug'
  151 |         debug(p);
      |         ^~~~~

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