oj.uz

답안 #634175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634175 2022-08-24T00:18:46 Z flappybird 수천개의 섬 (IOI22_islands) C++17
100 / 100
 134 ms 22948 KB 
#include "islands.h"

#include <bits/stdc++.h>
using namespace std;

#define MAX 201010

int deg[MAX];
vector<int> adj[MAX];
vector<int> radj[MAX];
int chk[MAX];
int vis[MAX];
vector<int> U, V;
int N, M;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	int i;
	::N = N;
	::M = M;
	::U = U;
	::V = V;
	for (i = 0; i < M; i++) deg[U[i]]++, adj[U[i]].push_back(i), radj[V[i]].push_back(U[i]);
	queue<int> q;
	for (i = 0; i < N; i++) if (!deg[i]) q.push(i);
	int s = 0;
	vector<int> st;
	while (1) {
		while (q.size()) {
			int t = q.front();
			chk[t] = 1;
			q.pop();
			for (auto v : radj[t]) if (!chk[v]) {
				deg[v]--;
				if (deg[v] == 0) q.push(v);
			}
		}
		if (deg[s] <= 1) {
			if (deg[s] == 0) return false;
			for (auto n : adj[s]) {
				if (!chk[V[n]]) {
					for (auto v : radj[s]) if (!chk[v]) {
						deg[v]--;
						if (deg[v] == 0) q.push(v);
					}
					chk[s] = 1;
					s = V[n];
					st.push_back(n);
					break;
				}
			}
			if (deg[s] == 0) return false;
			continue;
		}
		else break;
	}
	vector<int> ans = st;
	int a, b;
	a = b = -1;
	for (auto n : adj[s]) if (!chk[V[n]]) b = a, a = n;
	vector<int> p1, p2, cyc1, cyc2;
	int v;

	p1.push_back(a);
	v = V[a];
	vis[a] = 1;
	while (1) {
		int nn, x;
		for (auto n : adj[v]) {
			x = V[n];
			if (chk[x]) continue;
			nn = n;
			break;
		}
		if (vis[nn]) {
			while (p1.size()) {
				cyc1.push_back(p1.back());
				if (p1.back() == nn) {
					p1.pop_back();
					break;
				}
				p1.pop_back();
			}
			reverse(cyc1.begin(), cyc1.end());
			break;
		}
		p1.push_back(nn);
		vis[nn] = 1;
		v = x;
	}

end1:

	memset(vis, 0, sizeof(vis));

	p2.push_back(b);
	v = V[b];
	vis[b] = 1;
	while (1) {
		int nn, x;
		for (auto n : adj[v]) {
			x = V[n];
			if (chk[x]) continue;
			nn = n;
			break;
		}
		if (vis[nn]) {
			while (p2.size()) {
				cyc2.push_back(p2.back());
				if (p2.back() == nn) {
					p2.pop_back();
					break;
				}
				p2.pop_back();
			}
			reverse(cyc2.begin(), cyc2.end());
			break;
		}
		p2.push_back(nn);
		vis[nn] = 1;
		v = x;
	}

end2:

	memset(vis, 0, sizeof(vis));

	for (auto v : cyc1) vis[v] = 1;
	int c = 0;
	for (auto v : cyc2) if (vis[v]) c = 1;

	for (auto v : p1) ans.push_back(v);
	for (auto v : cyc1) ans.push_back(v);
	reverse(p1.begin(), p1.end());
	for (auto v : p1) ans.push_back(v);
	reverse(p1.begin(), p1.end());

	for (auto v : p2) ans.push_back(v);
	if (c) reverse(cyc2.begin(), cyc2.end());
	for (auto v : cyc2) ans.push_back(v);
	if (c) reverse(cyc2.begin(), cyc2.end());
	reverse(p2.begin(), p2.end());
	for (auto v : p2) ans.push_back(v);
	reverse(p2.begin(), p2.end());

	if (c) {
		reverse(st.begin(), st.end());
		for (auto v : st) ans.push_back(v);
		return ans;
	}

	for (auto v : p1) ans.push_back(v);
	reverse(cyc1.begin(), cyc1.end());
	for (auto v : cyc1) ans.push_back(v);
	reverse(cyc1.begin(), cyc1.end());
	reverse(p1.begin(), p1.end());
	for (auto v : p1) ans.push_back(v);
	reverse(p1.begin(), p1.end());

	for (auto v : p2) ans.push_back(v);
	reverse(cyc2.begin(), cyc2.end());
	for (auto v : cyc2) ans.push_back(v);
	reverse(cyc2.begin(), cyc2.end());
	reverse(p2.begin(), p2.end());
	for (auto v : p2) ans.push_back(v);
	reverse(p2.begin(), p2.end());

	reverse(st.begin(), st.end());
	for (auto v : st) ans.push_back(v);
	return ans;
}

Compilation message

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:91:1: warning: label 'end1' defined but not used [-Wunused-label]
   91 | end1:
      | ^~~~
islands.cpp:123:1: warning: label 'end2' defined but not used [-Wunused-label]
  123 | end2:
      | ^~~~
islands.cpp:120:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |   v = x;
      |   ~~^~~
islands.cpp:88:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |   v = x;
      |   ~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 42 ms 16888 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 36 ms 16076 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10728 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 10456 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 9752 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 6 ms 10580 KB Output is correct
11 Correct 5 ms 10452 KB Output is correct
12 Correct 6 ms 10624 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 6 ms 10452 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 24 ms 14032 KB Output is correct
18 Correct 21 ms 13524 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 10540 KB Output is correct
21 Correct 6 ms 10452 KB Output is correct
22 Correct 5 ms 10452 KB Output is correct
23 Correct 34 ms 16004 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10684 KB Output is correct
3 Correct 35 ms 16560 KB Output is correct
4 Correct 38 ms 16864 KB Output is correct
5 Correct 6 ms 10580 KB Output is correct
6 Correct 6 ms 10668 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 6 ms 10580 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct
13 Correct 7 ms 10704 KB Output is correct
14 Correct 7 ms 10672 KB Output is correct
15 Correct 6 ms 10712 KB Output is correct
16 Correct 6 ms 10584 KB Output is correct
17 Correct 5 ms 9688 KB Output is correct
18 Correct 6 ms 10720 KB Output is correct
19 Correct 6 ms 10592 KB Output is correct
20 Correct 41 ms 16848 KB Output is correct
21 Correct 40 ms 16940 KB Output is correct
22 Correct 5 ms 9888 KB Output is correct
23 Correct 6 ms 9824 KB Output is correct
24 Correct 5 ms 9696 KB Output is correct
25 Correct 6 ms 10580 KB Output is correct
26 Correct 6 ms 10580 KB Output is correct
27 Correct 39 ms 17128 KB Output is correct
28 Correct 41 ms 17284 KB Output is correct
29 Correct 5 ms 9684 KB Output is correct
30 Correct 43 ms 17220 KB Output is correct
31 Correct 5 ms 10452 KB Output is correct
32 Correct 38 ms 17108 KB Output is correct
33 Correct 37 ms 17136 KB Output is correct
34 Correct 26 ms 14000 KB Output is correct
35 Correct 6 ms 10580 KB Output is correct
36 Correct 33 ms 16272 KB Output is correct
37 Correct 39 ms 17676 KB Output is correct
38 Correct 5 ms 9812 KB Output is correct
39 Correct 33 ms 15500 KB Output is correct
40 Correct 6 ms 10580 KB Output is correct
41 Correct 43 ms 17216 KB Output is correct
42 Correct 39 ms 17264 KB Output is correct
43 Correct 5 ms 9684 KB Output is correct
44 Correct 6 ms 9812 KB Output is correct
45 Correct 7 ms 10708 KB Output is correct
46 Correct 21 ms 13476 KB Output is correct

Subtask #5
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 42 ms 16888 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 10452 KB Output is correct
11 Correct 5 ms 10452 KB Output is correct
12 Correct 6 ms 10452 KB Output is correct
13 Correct 36 ms 16076 KB Output is correct
14 Correct 6 ms 10728 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 10456 KB Output is correct
18 Correct 5 ms 9812 KB Output is correct
19 Correct 6 ms 10452 KB Output is correct
20 Correct 5 ms 9752 KB Output is correct
21 Correct 6 ms 10452 KB Output is correct
22 Correct 5 ms 10452 KB Output is correct
23 Correct 6 ms 10580 KB Output is correct
24 Correct 5 ms 10452 KB Output is correct
25 Correct 6 ms 10624 KB Output is correct
26 Correct 5 ms 9684 KB Output is correct
27 Correct 5 ms 9684 KB Output is correct
28 Correct 6 ms 10452 KB Output is correct
29 Correct 5 ms 9684 KB Output is correct
30 Correct 24 ms 14032 KB Output is correct
31 Correct 21 ms 13524 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 6 ms 10540 KB Output is correct
34 Correct 6 ms 10452 KB Output is correct
35 Correct 5 ms 10452 KB Output is correct
36 Correct 34 ms 16004 KB Output is correct
37 Correct 5 ms 10452 KB Output is correct
38 Correct 6 ms 9684 KB Output is correct
39 Correct 5 ms 9684 KB Output is correct
40 Correct 5 ms 9684 KB Output is correct
41 Correct 21 ms 12788 KB Output is correct
42 Correct 6 ms 9940 KB Output is correct
43 Correct 39 ms 15820 KB Output is correct
44 Correct 49 ms 15788 KB Output is correct
45 Correct 39 ms 16488 KB Output is correct
46 Correct 6 ms 10452 KB Output is correct
47 Correct 6 ms 10452 KB Output is correct
48 Correct 6 ms 10452 KB Output is correct
49 Correct 6 ms 10672 KB Output is correct
50 Correct 109 ms 22228 KB Output is correct
51 Correct 92 ms 21892 KB Output is correct
52 Correct 93 ms 21804 KB Output is correct
53 Correct 98 ms 22584 KB Output is correct
54 Correct 91 ms 21812 KB Output is correct
55 Correct 92 ms 21796 KB Output is correct
56 Correct 95 ms 22596 KB Output is correct
57 Correct 63 ms 20096 KB Output is correct
58 Correct 94 ms 21604 KB Output is correct
59 Correct 111 ms 20940 KB Output is correct
60 Correct 91 ms 20300 KB Output is correct
61 Correct 96 ms 20420 KB Output is correct
62 Correct 17 ms 12328 KB Output is correct
63 Correct 85 ms 20472 KB Output is correct
64 Correct 27 ms 14292 KB Output is correct
65 Correct 7 ms 10552 KB Output is correct
66 Correct 6 ms 10580 KB Output is correct
67 Correct 94 ms 21572 KB Output is correct
68 Correct 42 ms 17248 KB Output is correct
69 Correct 54 ms 17052 KB Output is correct
70 Correct 6 ms 10668 KB Output is correct
71 Correct 59 ms 16972 KB Output is correct
72 Correct 5 ms 10452 KB Output is correct
73 Correct 80 ms 19652 KB Output is correct
74 Correct 98 ms 22084 KB Output is correct
75 Correct 8 ms 10964 KB Output is correct
76 Correct 38 ms 15624 KB Output is correct
77 Correct 66 ms 19120 KB Output is correct
78 Correct 92 ms 20324 KB Output is correct
79 Correct 6 ms 10452 KB Output is correct
80 Correct 134 ms 22804 KB Output is correct
81 Correct 6 ms 10688 KB Output is correct
82 Correct 38 ms 16408 KB Output is correct
83 Correct 5 ms 10608 KB Output is correct
84 Correct 5 ms 10452 KB Output is correct
85 Correct 39 ms 15864 KB Output is correct
86 Correct 6 ms 10580 KB Output is correct
87 Correct 8 ms 10836 KB Output is correct
88 Correct 6 ms 10708 KB Output is correct
89 Correct 86 ms 20276 KB Output is correct
90 Correct 92 ms 20332 KB Output is correct
91 Correct 114 ms 22948 KB Output is correct
92 Correct 5 ms 10452 KB Output is correct