oj.uz

Submission #821653

# Submission time Handle Problem Language Result Execution time Memory
821653 2023-08-11T12:32:43 Z caganyanmaz Parachute rings (IOI12_rings) C++17
37 / 100
 1667 ms 181280 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 = 1e6;
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();
                        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);
        }
        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);
                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:185:9: note: in expansion of macro 'debug'
  185 |         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:213:9: note: in expansion of macro 'debug'
  213 |         debug(p);
      |         ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39472 KB Output is correct
2 Correct 18 ms 39764 KB Output is correct
3 Correct 19 ms 39820 KB Output is correct
4 Correct 17 ms 39552 KB Output is correct
5 Correct 18 ms 39940 KB Output is correct
6 Correct 20 ms 40400 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39932 KB Output is correct
9 Correct 23 ms 39720 KB Output is correct
10 Correct 21 ms 39892 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 82124 KB Output is correct
2 Correct 1167 ms 94136 KB Output is correct
3 Correct 375 ms 90812 KB Output is correct
4 Correct 1303 ms 121856 KB Output is correct
5 Correct 1382 ms 124308 KB Output is correct
6 Correct 1667 ms 181280 KB Output is correct
7 Correct 367 ms 90952 KB Output is correct
8 Correct 1140 ms 113456 KB Output is correct
9 Correct 1245 ms 120644 KB Output is correct
10 Correct 678 ms 120076 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39472 KB Output is correct
2 Correct 18 ms 39764 KB Output is correct
3 Correct 19 ms 39820 KB Output is correct
4 Correct 17 ms 39552 KB Output is correct
5 Correct 18 ms 39940 KB Output is correct
6 Correct 20 ms 40400 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39932 KB Output is correct
9 Correct 23 ms 39720 KB Output is correct
10 Correct 21 ms 39892 KB Output is correct
11 Correct 22 ms 39892 KB Output is correct
12 Correct 23 ms 40376 KB Output is correct
13 Correct 23 ms 40404 KB Output is correct
14 Runtime error 52 ms 81180 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 17 ms 39472 KB Output is correct
2 Correct 18 ms 39764 KB Output is correct
3 Correct 19 ms 39820 KB Output is correct
4 Correct 17 ms 39552 KB Output is correct
5 Correct 18 ms 39940 KB Output is correct
6 Correct 20 ms 40400 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39932 KB Output is correct
9 Correct 23 ms 39720 KB Output is correct
10 Correct 21 ms 39892 KB Output is correct
11 Correct 22 ms 39892 KB Output is correct
12 Correct 23 ms 40376 KB Output is correct
13 Correct 23 ms 40404 KB Output is correct
14 Runtime error 52 ms 81180 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 17 ms 39472 KB Output is correct
2 Correct 18 ms 39764 KB Output is correct
3 Correct 19 ms 39820 KB Output is correct
4 Correct 17 ms 39552 KB Output is correct
5 Correct 18 ms 39940 KB Output is correct
6 Correct 20 ms 40400 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39932 KB Output is correct
9 Correct 23 ms 39720 KB Output is correct
10 Correct 21 ms 39892 KB Output is correct
11 Correct 446 ms 82124 KB Output is correct
12 Correct 1167 ms 94136 KB Output is correct
13 Correct 375 ms 90812 KB Output is correct
14 Correct 1303 ms 121856 KB Output is correct
15 Correct 1382 ms 124308 KB Output is correct
16 Correct 1667 ms 181280 KB Output is correct
17 Correct 367 ms 90952 KB Output is correct
18 Correct 1140 ms 113456 KB Output is correct
19 Correct 1245 ms 120644 KB Output is correct
20 Correct 678 ms 120076 KB Output is correct
21 Correct 22 ms 39892 KB Output is correct
22 Correct 23 ms 40376 KB Output is correct
23 Correct 23 ms 40404 KB Output is correct
24 Runtime error 52 ms 81180 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -