oj.uz

Submission #821657

# Submission time Handle Problem Language Result Execution time Memory
821657 2023-08-11T12:39:14 Z caganyanmaz Parachute rings (IOI12_rings) C++17
37 / 100
 1677 ms 181360 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(); // 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 20 ms 39380 KB Output is correct
2 Correct 20 ms 39764 KB Output is correct
3 Correct 20 ms 39736 KB Output is correct
4 Correct 18 ms 39636 KB Output is correct
5 Correct 20 ms 39940 KB Output is correct
6 Correct 21 ms 40404 KB Output is correct
7 Correct 20 ms 39616 KB Output is correct
8 Correct 20 ms 39892 KB Output is correct
9 Correct 20 ms 39800 KB Output is correct
10 Correct 20 ms 39880 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 82228 KB Output is correct
2 Correct 1002 ms 94140 KB Output is correct
3 Correct 369 ms 90816 KB Output is correct
4 Correct 1225 ms 121776 KB Output is correct
5 Correct 1246 ms 124296 KB Output is correct
6 Correct 1677 ms 181360 KB Output is correct
7 Correct 349 ms 90888 KB Output is correct
8 Correct 1119 ms 113448 KB Output is correct
9 Correct 1223 ms 120712 KB Output is correct
10 Correct 667 ms 120068 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 20 ms 39764 KB Output is correct
3 Correct 20 ms 39736 KB Output is correct
4 Correct 18 ms 39636 KB Output is correct
5 Correct 20 ms 39940 KB Output is correct
6 Correct 21 ms 40404 KB Output is correct
7 Correct 20 ms 39616 KB Output is correct
8 Correct 20 ms 39892 KB Output is correct
9 Correct 20 ms 39800 KB Output is correct
10 Correct 20 ms 39880 KB Output is correct
11 Correct 20 ms 39892 KB Output is correct
12 Correct 24 ms 40352 KB Output is correct
13 Correct 22 ms 40316 KB Output is correct
14 Runtime error 53 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 20 ms 39380 KB Output is correct
2 Correct 20 ms 39764 KB Output is correct
3 Correct 20 ms 39736 KB Output is correct
4 Correct 18 ms 39636 KB Output is correct
5 Correct 20 ms 39940 KB Output is correct
6 Correct 21 ms 40404 KB Output is correct
7 Correct 20 ms 39616 KB Output is correct
8 Correct 20 ms 39892 KB Output is correct
9 Correct 20 ms 39800 KB Output is correct
10 Correct 20 ms 39880 KB Output is correct
11 Correct 20 ms 39892 KB Output is correct
12 Correct 24 ms 40352 KB Output is correct
13 Correct 22 ms 40316 KB Output is correct
14 Runtime error 53 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 20 ms 39380 KB Output is correct
2 Correct 20 ms 39764 KB Output is correct
3 Correct 20 ms 39736 KB Output is correct
4 Correct 18 ms 39636 KB Output is correct
5 Correct 20 ms 39940 KB Output is correct
6 Correct 21 ms 40404 KB Output is correct
7 Correct 20 ms 39616 KB Output is correct
8 Correct 20 ms 39892 KB Output is correct
9 Correct 20 ms 39800 KB Output is correct
10 Correct 20 ms 39880 KB Output is correct
11 Correct 336 ms 82228 KB Output is correct
12 Correct 1002 ms 94140 KB Output is correct
13 Correct 369 ms 90816 KB Output is correct
14 Correct 1225 ms 121776 KB Output is correct
15 Correct 1246 ms 124296 KB Output is correct
16 Correct 1677 ms 181360 KB Output is correct
17 Correct 349 ms 90888 KB Output is correct
18 Correct 1119 ms 113448 KB Output is correct
19 Correct 1223 ms 120712 KB Output is correct
20 Correct 667 ms 120068 KB Output is correct
21 Correct 20 ms 39892 KB Output is correct
22 Correct 24 ms 40352 KB Output is correct
23 Correct 22 ms 40316 KB Output is correct
24 Runtime error 53 ms 81180 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -