oj.uz

답안 #821666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821666 2023-08-11T12:46:48 Z caganyanmaz 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 1908 ms 220692 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 c : g[node])
                        if (p.find(c) != p.end())
                                p_new.insert(c);
        if (p.find(node) != p.end())
                p_new.insert(node);
        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:71:9: note: in expansion of macro 'debug'
   71 |         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:94:25: note: in expansion of macro 'debug'
   94 |                         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:121:17: note: in expansion of macro 'debug'
  121 |                 debug("start");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:128:17: note: in expansion of macro 'debug'
  128 |                 debug("a");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:134:17: note: in expansion of macro 'debug'
  134 |                 debug("b");
      |                 ^~~~~
rings.cpp:23:21: warning: statement has no effect [-Wunused-value]
   23 | #define debug(x...) 42
      |                     ^~
rings.cpp:159:17: note: in expansion of macro 'debug'
  159 |                 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:184:9: note: in expansion of macro 'debug'
  184 |         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:212:9: note: in expansion of macro 'debug'
  212 |         debug(p);
      |         ^~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 78548 KB Output is correct
2 Correct 33 ms 78948 KB Output is correct
3 Correct 33 ms 78868 KB Output is correct
4 Correct 33 ms 78892 KB Output is correct
5 Correct 35 ms 79216 KB Output is correct
6 Correct 34 ms 79692 KB Output is correct
7 Correct 35 ms 78852 KB Output is correct
8 Correct 34 ms 79104 KB Output is correct
9 Correct 35 ms 78924 KB Output is correct
10 Correct 36 ms 79060 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 365 ms 121432 KB Output is correct
2 Correct 943 ms 133280 KB Output is correct
3 Correct 382 ms 129952 KB Output is correct
4 Correct 1311 ms 161040 KB Output is correct
5 Correct 1408 ms 163668 KB Output is correct
6 Correct 1908 ms 220692 KB Output is correct
7 Correct 362 ms 130092 KB Output is correct
8 Correct 1201 ms 152616 KB Output is correct
9 Correct 1187 ms 159852 KB Output is correct
10 Correct 693 ms 159404 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 78548 KB Output is correct
2 Correct 33 ms 78948 KB Output is correct
3 Correct 33 ms 78868 KB Output is correct
4 Correct 33 ms 78892 KB Output is correct
5 Correct 35 ms 79216 KB Output is correct
6 Correct 34 ms 79692 KB Output is correct
7 Correct 35 ms 78852 KB Output is correct
8 Correct 34 ms 79104 KB Output is correct
9 Correct 35 ms 78924 KB Output is correct
10 Correct 36 ms 79060 KB Output is correct
11 Correct 34 ms 79128 KB Output is correct
12 Correct 37 ms 79600 KB Output is correct
13 Correct 36 ms 79560 KB Output is correct
14 Runtime error 91 ms 160844 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 78548 KB Output is correct
2 Correct 33 ms 78948 KB Output is correct
3 Correct 33 ms 78868 KB Output is correct
4 Correct 33 ms 78892 KB Output is correct
5 Correct 35 ms 79216 KB Output is correct
6 Correct 34 ms 79692 KB Output is correct
7 Correct 35 ms 78852 KB Output is correct
8 Correct 34 ms 79104 KB Output is correct
9 Correct 35 ms 78924 KB Output is correct
10 Correct 36 ms 79060 KB Output is correct
11 Correct 34 ms 79128 KB Output is correct
12 Correct 37 ms 79600 KB Output is correct
13 Correct 36 ms 79560 KB Output is correct
14 Runtime error 91 ms 160844 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 78548 KB Output is correct
2 Correct 33 ms 78948 KB Output is correct
3 Correct 33 ms 78868 KB Output is correct
4 Correct 33 ms 78892 KB Output is correct
5 Correct 35 ms 79216 KB Output is correct
6 Correct 34 ms 79692 KB Output is correct
7 Correct 35 ms 78852 KB Output is correct
8 Correct 34 ms 79104 KB Output is correct
9 Correct 35 ms 78924 KB Output is correct
10 Correct 36 ms 79060 KB Output is correct
11 Correct 365 ms 121432 KB Output is correct
12 Correct 943 ms 133280 KB Output is correct
13 Correct 382 ms 129952 KB Output is correct
14 Correct 1311 ms 161040 KB Output is correct
15 Correct 1408 ms 163668 KB Output is correct
16 Correct 1908 ms 220692 KB Output is correct
17 Correct 362 ms 130092 KB Output is correct
18 Correct 1201 ms 152616 KB Output is correct
19 Correct 1187 ms 159852 KB Output is correct
20 Correct 693 ms 159404 KB Output is correct
21 Correct 34 ms 79128 KB Output is correct
22 Correct 37 ms 79600 KB Output is correct
23 Correct 36 ms 79560 KB Output is correct
24 Runtime error 91 ms 160844 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -