Submission #821486

# Submission time Handle Problem Language Result Execution time Memory
821486 2023-08-11T10:49:18 Z caganyanmaz Parachute rings (IOI12_rings) C++17
0 / 100
4000 ms 69308 KB
#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

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);
      |         ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 19 ms 39668 KB Output is correct
3 Correct 20 ms 39724 KB Output is correct
4 Incorrect 23 ms 39596 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 262 ms 59108 KB Output is correct
2 Correct 750 ms 69308 KB Output is correct
3 Execution timed out 4088 ms 67756 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 19 ms 39668 KB Output is correct
3 Correct 20 ms 39724 KB Output is correct
4 Incorrect 23 ms 39596 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 19 ms 39668 KB Output is correct
3 Correct 20 ms 39724 KB Output is correct
4 Incorrect 23 ms 39596 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 19 ms 39668 KB Output is correct
3 Correct 20 ms 39724 KB Output is correct
4 Incorrect 23 ms 39596 KB Output isn't correct
5 Halted 0 ms 0 KB -