oj.uz

Submission #821660

# Submission time Handle Problem Language Result Execution time Memory
821660 2023-08-11T12:41:59 Z caganyanmaz Parachute rings (IOI12_rings) C++17
37 / 100
 1740 ms 220760 KB 
#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;



void __print(const char* s) { cerr << s; }
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 = 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)
{
        if (g[node].size() <= 2 || g[node].size() >= 5)
                return;
        set<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.insert(i);
        if (g[node].size() == 4)
                for (int i : p)
                        if (i == node)
                                p_new.insert(i);
        debug(node, p_new);
        p = p_new;

}

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))
                {
                        debug(node, c);
                        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)
        {
                debug("start");
                dfs(a, b);
                visited.reset();
                assign_pred(a, -1); // Create predecessors
        }
        else if (in_loop[a] && in_loop[b])
        {
                debug("a");
                current_a.insert(a);
                current_a.insert(b);
        }
        else if(!in_loop[a] && !in_loop[b])
        {
                debug("b");
                int i = a;
                for (; i != -1 && i != b && !in_loop[i]; i = pred[i])
                        in_loop[i] = true;
                if (i == b)
                {
                        p.clear(); // Means two seperate
                        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);
                // Finding two endpoints (they might the be same)
        }
        else
        {
                debug("c");
                if (in_loop[b]) swap(a, b);
                assert(b != -1);
                for (; !in_loop[b]; b = pred[b])
                {
                        assert(b != -1); // It shouldn't happen since there is a loop in b's component
                        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())
                        it = current_a.erase(it);
                else
                        it++;
        p = current_a;
        visited_loop = true;

}

void Link(int a, int b)
{
        if (p.empty())
                return;
        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);
                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()
{
        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 'void check(int)':
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:73:9: note: in expansion of macro 'debug'
   73 |         debug(node, p_new);
      |         ^~~~~
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:96:25: note: in expansion of macro 'debug'
   96 |                         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:123:17: note: in expansion of macro 'debug'
  123 |                 debug("start");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:130:17: note: in expansion of macro 'debug'
  130 |                 debug("a");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:136:17: note: in expansion of macro 'debug'
  136 |                 debug("b");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:161:17: note: in expansion of macro 'debug'
  161 |                 debug("c");
      |                 ^~~~~
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:186:9: note: in expansion of macro 'debug'
  186 |         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:214:9: note: in expansion of macro 'debug'
  214 |         debug(p);
      |         ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78540 KB Output is correct
2 Correct 39 ms 78844 KB Output is correct
3 Correct 36 ms 78900 KB Output is correct
4 Correct 41 ms 78824 KB Output is correct
5 Correct 35 ms 79252 KB Output is correct
6 Correct 36 ms 79668 KB Output is correct
7 Correct 40 ms 78744 KB Output is correct
8 Correct 40 ms 79188 KB Output is correct
9 Correct 36 ms 78976 KB Output is correct
10 Correct 37 ms 79008 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 121328 KB Output is correct
2 Correct 939 ms 133280 KB Output is correct
3 Correct 401 ms 129896 KB Output is correct
4 Correct 1208 ms 161132 KB Output is correct
5 Correct 1227 ms 163696 KB Output is correct
6 Correct 1740 ms 220760 KB Output is correct
7 Correct 374 ms 129996 KB Output is correct
8 Correct 1094 ms 152564 KB Output is correct
9 Correct 1234 ms 159916 KB Output is correct
10 Correct 728 ms 159512 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78540 KB Output is correct
2 Correct 39 ms 78844 KB Output is correct
3 Correct 36 ms 78900 KB Output is correct
4 Correct 41 ms 78824 KB Output is correct
5 Correct 35 ms 79252 KB Output is correct
6 Correct 36 ms 79668 KB Output is correct
7 Correct 40 ms 78744 KB Output is correct
8 Correct 40 ms 79188 KB Output is correct
9 Correct 36 ms 78976 KB Output is correct
10 Correct 37 ms 79008 KB Output is correct
11 Correct 36 ms 79188 KB Output is correct
12 Correct 39 ms 79584 KB Output is correct
13 Correct 39 ms 79664 KB Output is correct
14 Runtime error 98 ms 160860 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78540 KB Output is correct
2 Correct 39 ms 78844 KB Output is correct
3 Correct 36 ms 78900 KB Output is correct
4 Correct 41 ms 78824 KB Output is correct
5 Correct 35 ms 79252 KB Output is correct
6 Correct 36 ms 79668 KB Output is correct
7 Correct 40 ms 78744 KB Output is correct
8 Correct 40 ms 79188 KB Output is correct
9 Correct 36 ms 78976 KB Output is correct
10 Correct 37 ms 79008 KB Output is correct
11 Correct 36 ms 79188 KB Output is correct
12 Correct 39 ms 79584 KB Output is correct
13 Correct 39 ms 79664 KB Output is correct
14 Runtime error 98 ms 160860 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78540 KB Output is correct
2 Correct 39 ms 78844 KB Output is correct
3 Correct 36 ms 78900 KB Output is correct
4 Correct 41 ms 78824 KB Output is correct
5 Correct 35 ms 79252 KB Output is correct
6 Correct 36 ms 79668 KB Output is correct
7 Correct 40 ms 78744 KB Output is correct
8 Correct 40 ms 79188 KB Output is correct
9 Correct 36 ms 78976 KB Output is correct
10 Correct 37 ms 79008 KB Output is correct
11 Correct 376 ms 121328 KB Output is correct
12 Correct 939 ms 133280 KB Output is correct
13 Correct 401 ms 129896 KB Output is correct
14 Correct 1208 ms 161132 KB Output is correct
15 Correct 1227 ms 163696 KB Output is correct
16 Correct 1740 ms 220760 KB Output is correct
17 Correct 374 ms 129996 KB Output is correct
18 Correct 1094 ms 152564 KB Output is correct
19 Correct 1234 ms 159916 KB Output is correct
20 Correct 728 ms 159512 KB Output is correct
21 Correct 36 ms 79188 KB Output is correct
22 Correct 39 ms 79584 KB Output is correct
23 Correct 39 ms 79664 KB Output is correct
24 Runtime error 98 ms 160860 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -