oj.uz

Submission #736513

# Submission time Handle Problem Language Result Execution time Memory
736513 2023-05-05T20:30:51 Z puppy Thousands Islands (IOI22_islands) C++17
100 / 100
 286 ms 35780 KB 
#include "islands.h"

#include <variant>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
#include <iostream>
#include <set>
#include <queue>
using namespace std;
set<int> out[100005];
set<int> in[100005];
bool removed[100005];
bool visited[100005];
bool cycle[100005];
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
        for (int i = 0; i < M; i++) {
            out[U[i]].insert(i);
            in[V[i]].insert(i);
        }
        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (out[i].empty()) {
                removed[i] = true;
                q.push(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == 0) return false;
            for (int k:in[cur]) {
                out[U[k]].erase(k);
                if (!removed[U[k]] && out[U[k]].empty()) {
                    removed[U[k]] = true;
                    q.push(U[k]);
                }
            }
            in[cur].clear();
        }
        int st = 0;
        vector<int> v;
        while (1) {
            if (out[st].size() >= 2) break;
            else if (removed[st] || out[st].empty()) return false;
            queue<int> q;
            q.push(st);
            removed[st] = true;
            while (!q.empty()) {
                int cur = q.front(); q.pop();
                for (int k:in[cur]) {
                    if (removed[U[k]]) continue;
                    out[U[k]].erase(k);
                    if (out[U[k]].empty()) {
                        removed[U[k]] = true;
                        q.push(U[k]);
                    }
                }
            }
            v.push_back(*out[st].begin());
            st = V[v.back()];
        }
        for (int i = 0; i < N; i++) {
            if (removed[i]) continue;
            vector<int> to_remove;
            auto it = ++out[i].begin();
            if (i == st) ++it;
            for (;it != out[i].end(); ++it) to_remove.push_back(*it);
            for (int k:to_remove) out[i].erase(k);
        }
        visited[st] = true;
        vector<int> t1;
        t1.push_back(*out[st].begin());
        int _end = -1;
        while (1) {
            int cur = V[t1.back()];
            visited[cur] = true;
            int nxt = *out[cur].begin();
            t1.push_back(nxt);
            if (visited[V[nxt]]) {
                _end = V[nxt];
                break;
            }
            else {
                cur = V[nxt];
            }
        }
        vector<int> str, cyc;
        bool flag = false;
        for (int i:t1) {
            flag |= U[i] == _end;
            if (flag) cyc.push_back(i);
            else str.push_back(i);
        }
        for (int i:cyc) cycle[U[i]] = true;
        fill(visited, visited + 100005, false);
        vector<int> t2;
        visited[st] = true;
        t2.push_back(*++out[st].begin());
        _end = -1;
        while (1) {
            int cur = V[t2.back()];
            if (cycle[cur]) {
                vector<int> ans;
                for (int i:v) ans.push_back(i);
                for (int i:str) ans.push_back(i);
                for (int i:cyc) ans.push_back(i);
                reverse(str.begin(), str.end());
                for (int i:str) ans.push_back(i);
                for (int i:t2) ans.push_back(i);
                int pos = 0;
                while (V[cyc[pos]] != cur) pos++;
                for (int i = pos; i > pos - (int)cyc.size(); i--) {
                    ans.push_back(cyc[(i + (int)cyc.size()) % cyc.size()]);
                }
                reverse(t2.begin(), t2.end());
                for (int i:t2) ans.push_back(i);
                reverse(v.begin(), v.end());
                for (int i:v) ans.push_back(i);
                return ans;
            }
            visited[cur] = true;
            int nxt = *out[cur].begin();
            t2.push_back(nxt);
            if (visited[V[nxt]]) {
                _end = V[nxt];
                break;
            }
            else {
                cur = V[nxt];
            }
        }
        vector<int> str2, cyc2;
        flag = false;
        for (int i:t2) {
            flag |= U[i] == _end;
            if (flag) cyc2.push_back(i);
            else str2.push_back(i);
        }
        vector<int> ans;
        for (int i:v) ans.push_back(i);
        for (int i:str) ans.push_back(i);
        for (int i:cyc) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        for (int i:str2) ans.push_back(i);
        for (int i:cyc2) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        reverse(cyc.begin(), cyc.end());
        for (int i:cyc) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(cyc2.begin(), cyc2.end());
        for (int i:cyc2) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(v.begin(), v.end());
        for (int i:v) ans.push_back(i);
        return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 136 ms 32492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 129 ms 27208 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10196 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 9 ms 9844 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 7 ms 9824 KB Output is correct
8 Correct 5 ms 9832 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 7 ms 9968 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 8 ms 9960 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 8 ms 9648 KB Output is correct
17 Correct 93 ms 21472 KB Output is correct
18 Correct 67 ms 19084 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9696 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 6 ms 9812 KB Output is correct
23 Correct 155 ms 28400 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9828 KB Output is correct
2 Correct 6 ms 10184 KB Output is correct
3 Correct 174 ms 29420 KB Output is correct
4 Correct 170 ms 29516 KB Output is correct
5 Correct 7 ms 10168 KB Output is correct
6 Correct 6 ms 10196 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 5 ms 9796 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 7 ms 10068 KB Output is correct
12 Correct 7 ms 10196 KB Output is correct
13 Correct 7 ms 10196 KB Output is correct
14 Correct 8 ms 10196 KB Output is correct
15 Correct 7 ms 10452 KB Output is correct
16 Correct 6 ms 9976 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 7 ms 10160 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 202 ms 31560 KB Output is correct
21 Correct 184 ms 29428 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 5 ms 9812 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 6 ms 9940 KB Output is correct
26 Correct 6 ms 10068 KB Output is correct
27 Correct 174 ms 30504 KB Output is correct
28 Correct 217 ms 30608 KB Output is correct
29 Correct 5 ms 9664 KB Output is correct
30 Correct 209 ms 31624 KB Output is correct
31 Correct 7 ms 9684 KB Output is correct
32 Correct 204 ms 29420 KB Output is correct
33 Correct 210 ms 30524 KB Output is correct
34 Correct 92 ms 20704 KB Output is correct
35 Correct 6 ms 9940 KB Output is correct
36 Correct 166 ms 27356 KB Output is correct
37 Correct 173 ms 30516 KB Output is correct
38 Correct 7 ms 9840 KB Output is correct
39 Correct 165 ms 26564 KB Output is correct
40 Correct 6 ms 10068 KB Output is correct
41 Correct 238 ms 31628 KB Output is correct
42 Correct 248 ms 30520 KB Output is correct
43 Correct 5 ms 9684 KB Output is correct
44 Correct 7 ms 10068 KB Output is correct
45 Correct 6 ms 10068 KB Output is correct
46 Correct 51 ms 18532 KB Output is correct

Subtask #5
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 136 ms 32492 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 129 ms 27208 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 9 ms 9844 KB Output is correct
19 Correct 7 ms 9812 KB Output is correct
20 Correct 7 ms 9824 KB Output is correct
21 Correct 5 ms 9832 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 7 ms 9968 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 8 ms 9960 KB Output is correct
26 Correct 5 ms 9696 KB Output is correct
27 Correct 5 ms 9684 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Correct 8 ms 9648 KB Output is correct
30 Correct 93 ms 21472 KB Output is correct
31 Correct 67 ms 19084 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 5 ms 9696 KB Output is correct
34 Correct 5 ms 9684 KB Output is correct
35 Correct 6 ms 9812 KB Output is correct
36 Correct 155 ms 28400 KB Output is correct
37 Correct 5 ms 9812 KB Output is correct
38 Correct 6 ms 9700 KB Output is correct
39 Correct 6 ms 9636 KB Output is correct
40 Correct 5 ms 9704 KB Output is correct
41 Correct 95 ms 20108 KB Output is correct
42 Correct 8 ms 10284 KB Output is correct
43 Correct 110 ms 21848 KB Output is correct
44 Correct 103 ms 21728 KB Output is correct
45 Correct 95 ms 21856 KB Output is correct
46 Correct 5 ms 9700 KB Output is correct
47 Correct 6 ms 9812 KB Output is correct
48 Correct 6 ms 9696 KB Output is correct
49 Correct 7 ms 9940 KB Output is correct
50 Correct 125 ms 24924 KB Output is correct
51 Correct 240 ms 33516 KB Output is correct
52 Correct 240 ms 33720 KB Output is correct
53 Correct 240 ms 33756 KB Output is correct
54 Correct 250 ms 34156 KB Output is correct
55 Correct 214 ms 34036 KB Output is correct
56 Correct 215 ms 34032 KB Output is correct
57 Correct 161 ms 33768 KB Output is correct
58 Correct 130 ms 24968 KB Output is correct
59 Correct 237 ms 34148 KB Output is correct
60 Correct 274 ms 34156 KB Output is correct
61 Correct 238 ms 34132 KB Output is correct
62 Correct 24 ms 13568 KB Output is correct
63 Correct 164 ms 32856 KB Output is correct
64 Correct 142 ms 21528 KB Output is correct
65 Correct 5 ms 9812 KB Output is correct
66 Correct 6 ms 9812 KB Output is correct
67 Correct 219 ms 34212 KB Output is correct
68 Correct 283 ms 33100 KB Output is correct
69 Correct 98 ms 22060 KB Output is correct
70 Correct 6 ms 9968 KB Output is correct
71 Correct 189 ms 28008 KB Output is correct
72 Correct 6 ms 9812 KB Output is correct
73 Correct 264 ms 34124 KB Output is correct
74 Correct 112 ms 23992 KB Output is correct
75 Correct 11 ms 10992 KB Output is correct
76 Correct 52 ms 16852 KB Output is correct
77 Correct 89 ms 21936 KB Output is correct
78 Correct 285 ms 34164 KB Output is correct
79 Correct 6 ms 9684 KB Output is correct
80 Correct 257 ms 35780 KB Output is correct
81 Correct 5 ms 9940 KB Output is correct
82 Correct 198 ms 32340 KB Output is correct
83 Correct 5 ms 9812 KB Output is correct
84 Correct 5 ms 9812 KB Output is correct
85 Correct 46 ms 17000 KB Output is correct
86 Correct 6 ms 9940 KB Output is correct
87 Correct 7 ms 10324 KB Output is correct
88 Correct 10 ms 10324 KB Output is correct
89 Correct 220 ms 34160 KB Output is correct
90 Correct 254 ms 34132 KB Output is correct
91 Correct 286 ms 35432 KB Output is correct
92 Correct 5 ms 9812 KB Output is correct