oj.uz

답안 #821690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821690 2023-08-11T13:14:24 Z caganyanmaz 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 1975 ms 221856 KB 
#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;
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)
{
 		assert(node != -1);
        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);
        p.clear();
        p.insert(p_new.begin(), p_new.end());
}
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))
                        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)
        {
                dfs(a, b);
                visited.reset();
                assign_pred(a, -1);
        }
        else if (in_loop[a] && in_loop[b])
        {
                current_a.insert(a);
                current_a.insert(b);
        }
        else if(!in_loop[a] && !in_loop[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);
        }
        else
        {
                if (in_loop[b]) swap(a, b);
          		assert(in_loop[a] && !in_loop[b]);
                assert(b != -1);
                for (; !in_loop[b]; b = pred[b])
                {
                        assert(b != -1); 
                  		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())
                        current_a.erase(it++);
  				else
                  it++;
        }
        p.clear();
        p.insert(current_a.begin(), current_a.end());
        visited_loop = true;
}
void Link(int a, int b)
{
        if (p.empty())
                return;
        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()
{
        return p.size();

}
void merge(int a, int b)
{
        assert(b != -1 && a != -1);
        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;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 78564 KB Output is correct
2 Correct 41 ms 78988 KB Output is correct
3 Correct 42 ms 79024 KB Output is correct
4 Correct 41 ms 78924 KB Output is correct
5 Correct 42 ms 79268 KB Output is correct
6 Correct 42 ms 79716 KB Output is correct
7 Correct 40 ms 78816 KB Output is correct
8 Correct 42 ms 79132 KB Output is correct
9 Correct 42 ms 78936 KB Output is correct
10 Correct 48 ms 79064 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 424 ms 122868 KB Output is correct
2 Correct 985 ms 134636 KB Output is correct
3 Correct 369 ms 131912 KB Output is correct
4 Correct 1393 ms 162108 KB Output is correct
5 Correct 1376 ms 164920 KB Output is correct
6 Correct 1975 ms 221856 KB Output is correct
7 Correct 390 ms 131372 KB Output is correct
8 Correct 1204 ms 153784 KB Output is correct
9 Correct 1333 ms 161140 KB Output is correct
10 Correct 823 ms 160636 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 78564 KB Output is correct
2 Correct 41 ms 78988 KB Output is correct
3 Correct 42 ms 79024 KB Output is correct
4 Correct 41 ms 78924 KB Output is correct
5 Correct 42 ms 79268 KB Output is correct
6 Correct 42 ms 79716 KB Output is correct
7 Correct 40 ms 78816 KB Output is correct
8 Correct 42 ms 79132 KB Output is correct
9 Correct 42 ms 78936 KB Output is correct
10 Correct 48 ms 79064 KB Output is correct
11 Correct 41 ms 79188 KB Output is correct
12 Correct 48 ms 79748 KB Output is correct
13 Correct 47 ms 79648 KB Output is correct
14 Runtime error 108 ms 160816 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 78564 KB Output is correct
2 Correct 41 ms 78988 KB Output is correct
3 Correct 42 ms 79024 KB Output is correct
4 Correct 41 ms 78924 KB Output is correct
5 Correct 42 ms 79268 KB Output is correct
6 Correct 42 ms 79716 KB Output is correct
7 Correct 40 ms 78816 KB Output is correct
8 Correct 42 ms 79132 KB Output is correct
9 Correct 42 ms 78936 KB Output is correct
10 Correct 48 ms 79064 KB Output is correct
11 Correct 41 ms 79188 KB Output is correct
12 Correct 48 ms 79748 KB Output is correct
13 Correct 47 ms 79648 KB Output is correct
14 Runtime error 108 ms 160816 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 78564 KB Output is correct
2 Correct 41 ms 78988 KB Output is correct
3 Correct 42 ms 79024 KB Output is correct
4 Correct 41 ms 78924 KB Output is correct
5 Correct 42 ms 79268 KB Output is correct
6 Correct 42 ms 79716 KB Output is correct
7 Correct 40 ms 78816 KB Output is correct
8 Correct 42 ms 79132 KB Output is correct
9 Correct 42 ms 78936 KB Output is correct
10 Correct 48 ms 79064 KB Output is correct
11 Correct 424 ms 122868 KB Output is correct
12 Correct 985 ms 134636 KB Output is correct
13 Correct 369 ms 131912 KB Output is correct
14 Correct 1393 ms 162108 KB Output is correct
15 Correct 1376 ms 164920 KB Output is correct
16 Correct 1975 ms 221856 KB Output is correct
17 Correct 390 ms 131372 KB Output is correct
18 Correct 1204 ms 153784 KB Output is correct
19 Correct 1333 ms 161140 KB Output is correct
20 Correct 823 ms 160636 KB Output is correct
21 Correct 41 ms 79188 KB Output is correct
22 Correct 48 ms 79748 KB Output is correct
23 Correct 47 ms 79648 KB Output is correct
24 Runtime error 108 ms 160816 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -