oj.uz

Submission #821648

# Submission time Handle Problem Language Result Execution time Memory
821648 2023-08-11T12:30:18 Z caganyanmaz Parachute rings (IOI12_rings) C++17
37 / 100
 1965 ms 184820 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)
{
        if (node == target)
        {
                current_a.insert(node);
                in_loop[node] = true;
                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.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 20 ms 39380 KB Output is correct
2 Correct 23 ms 39764 KB Output is correct
3 Correct 20 ms 39884 KB Output is correct
4 Correct 18 ms 39592 KB Output is correct
5 Correct 19 ms 40056 KB Output is correct
6 Correct 20 ms 40384 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39952 KB Output is correct
9 Correct 21 ms 39892 KB Output is correct
10 Correct 20 ms 39832 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 82692 KB Output is correct
2 Correct 992 ms 94668 KB Output is correct
3 Correct 382 ms 91416 KB Output is correct
4 Correct 1275 ms 122300 KB Output is correct
5 Correct 1278 ms 127744 KB Output is correct
6 Correct 1965 ms 184820 KB Output is correct
7 Correct 384 ms 94408 KB Output is correct
8 Correct 1196 ms 116796 KB Output is correct
9 Correct 1366 ms 124160 KB Output is correct
10 Correct 727 ms 123668 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39380 KB Output is correct
2 Correct 23 ms 39764 KB Output is correct
3 Correct 20 ms 39884 KB Output is correct
4 Correct 18 ms 39592 KB Output is correct
5 Correct 19 ms 40056 KB Output is correct
6 Correct 20 ms 40384 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39952 KB Output is correct
9 Correct 21 ms 39892 KB Output is correct
10 Correct 20 ms 39832 KB Output is correct
11 Correct 22 ms 40020 KB Output is correct
12 Correct 22 ms 40444 KB Output is correct
13 Correct 21 ms 40436 KB Output is correct
14 Runtime error 51 ms 81240 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 20 ms 39380 KB Output is correct
2 Correct 23 ms 39764 KB Output is correct
3 Correct 20 ms 39884 KB Output is correct
4 Correct 18 ms 39592 KB Output is correct
5 Correct 19 ms 40056 KB Output is correct
6 Correct 20 ms 40384 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39952 KB Output is correct
9 Correct 21 ms 39892 KB Output is correct
10 Correct 20 ms 39832 KB Output is correct
11 Correct 22 ms 40020 KB Output is correct
12 Correct 22 ms 40444 KB Output is correct
13 Correct 21 ms 40436 KB Output is correct
14 Runtime error 51 ms 81240 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 20 ms 39380 KB Output is correct
2 Correct 23 ms 39764 KB Output is correct
3 Correct 20 ms 39884 KB Output is correct
4 Correct 18 ms 39592 KB Output is correct
5 Correct 19 ms 40056 KB Output is correct
6 Correct 20 ms 40384 KB Output is correct
7 Correct 18 ms 39636 KB Output is correct
8 Correct 19 ms 39952 KB Output is correct
9 Correct 21 ms 39892 KB Output is correct
10 Correct 20 ms 39832 KB Output is correct
11 Correct 368 ms 82692 KB Output is correct
12 Correct 992 ms 94668 KB Output is correct
13 Correct 382 ms 91416 KB Output is correct
14 Correct 1275 ms 122300 KB Output is correct
15 Correct 1278 ms 127744 KB Output is correct
16 Correct 1965 ms 184820 KB Output is correct
17 Correct 384 ms 94408 KB Output is correct
18 Correct 1196 ms 116796 KB Output is correct
19 Correct 1366 ms 124160 KB Output is correct
20 Correct 727 ms 123668 KB Output is correct
21 Correct 22 ms 40020 KB Output is correct
22 Correct 22 ms 40444 KB Output is correct
23 Correct 21 ms 40436 KB Output is correct
24 Runtime error 51 ms 81240 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -