oj.uz

Submission #821556

# Submission time Handle Problem Language Result Execution time Memory
821556 2023-08-11T11:32:38 Z caganyanmaz Parachute rings (IOI12_rings) C++17
20 / 100
 773 ms 133896 KB 
#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;




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;

vector<int> p;
vector<int> g[MXN];
Node node[MXN];
bitset<MXN> in_loop;
vector<int> touching_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;
int visited[MXN];
bool visited_loop = false;
int counter = 0;
int lll = 1;

bool dfs(int node, int target)
{
        if (in_loop[node] || (node == target && !visited_loop))
        {
                current_a.pb(node);
                in_loop[node] = true;
                return true;
        }
        if (node == target)
        {
                in_loop[node] = true;
                return true;
        }
        bool valid = false;
        visited[node] = lll;
        for (int c : g[node])
        {
                if (visited[c] != lll && dfs(c, target))
                {
                        debug(node, c);
                        valid = true;
                }
        }
        if (valid && !visited_loop)
                current_a.pb(node);
        if (valid)
                in_loop[node] = true;
        return valid;
}

void check(int a, int b)
{
        current_a.clear();
        if (!in_loop[a] && !in_loop[b])
        {
                dfs(a, b);
                if (visited_loop)
                {
                        dfs(b, a);
                        assert(current_a.size() <= 2);
                        if (current_a.size() <= 1)
                                current_a.clear();
                        if (current_a[0] == current_a[1])
                                current_a.pop_back();
                }
        }
        else if (in_loop[a] && in_loop[b])
        {
                current_a.pb(a);
                current_a.pb(b);
        }
        else  // One in loop, one out loop
        {
                if (!in_loop[a]) swap(a, b);
                debug(b, a, (bool)in_loop[0]);
                dfs(b, a);
                debug(current_a);
        }

        sort(current_a.begin(), current_a.end());
        debug(current_a);
        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;
        lll++;
        visited_loop = true;

}

void Link(int a, int b)
{
        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);
}

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:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:103:25: note: in expansion of macro 'debug'
  103 |                         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:138:17: note: in expansion of macro 'debug'
  138 |                 debug(b, a, (bool)in_loop[0]);
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:140:17: note: in expansion of macro 'debug'
  140 |                 debug(current_a);
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:144:9: note: in expansion of macro 'debug'
  144 |         debug(current_a);
      |         ^~~~~
rings.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while (i < current_a.size() && j < p.size())
      |                ~~^~~~~~~~~~~~~~~~~~
rings.cpp:147:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while (i < current_a.size() && j < p.size())
      |                                        ~~^~~~~~~~~~
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:171:9: note: in expansion of macro 'debug'
  171 |         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:184:9: note: in expansion of macro 'debug'
  184 |         debug(p);
      |         ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39440 KB Output is correct
2 Correct 19 ms 39572 KB Output is correct
3 Correct 19 ms 39624 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 19 ms 39680 KB Output is correct
6 Correct 20 ms 40020 KB Output is correct
7 Correct 18 ms 39472 KB Output is correct
8 Correct 20 ms 39688 KB Output is correct
9 Correct 19 ms 39672 KB Output is correct
10 Correct 19 ms 39620 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 58208 KB Output is correct
2 Correct 773 ms 68128 KB Output is correct
3 Runtime error 400 ms 133896 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39440 KB Output is correct
2 Correct 19 ms 39572 KB Output is correct
3 Correct 19 ms 39624 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 19 ms 39680 KB Output is correct
6 Correct 20 ms 40020 KB Output is correct
7 Correct 18 ms 39472 KB Output is correct
8 Correct 20 ms 39688 KB Output is correct
9 Correct 19 ms 39672 KB Output is correct
10 Correct 19 ms 39620 KB Output is correct
11 Runtime error 52 ms 80328 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39440 KB Output is correct
2 Correct 19 ms 39572 KB Output is correct
3 Correct 19 ms 39624 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 19 ms 39680 KB Output is correct
6 Correct 20 ms 40020 KB Output is correct
7 Correct 18 ms 39472 KB Output is correct
8 Correct 20 ms 39688 KB Output is correct
9 Correct 19 ms 39672 KB Output is correct
10 Correct 19 ms 39620 KB Output is correct
11 Runtime error 52 ms 80328 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39440 KB Output is correct
2 Correct 19 ms 39572 KB Output is correct
3 Correct 19 ms 39624 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 19 ms 39680 KB Output is correct
6 Correct 20 ms 40020 KB Output is correct
7 Correct 18 ms 39472 KB Output is correct
8 Correct 20 ms 39688 KB Output is correct
9 Correct 19 ms 39672 KB Output is correct
10 Correct 19 ms 39620 KB Output is correct
11 Correct 289 ms 58208 KB Output is correct
12 Correct 773 ms 68128 KB Output is correct
13 Runtime error 400 ms 133896 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -