답안 #772670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772670	2023-07-04T10:14:05 Z	marvinthang	수천개의 섬 (IOI22_islands)	C++17	100 / 100	259 ms	36520 KB

islands

/*************************************
*    author: marvinthang             *
*    created: 04.07.2023 16:55:32    *
*************************************/

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
		#include "debug.h"
#else
		#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
		#define DB(...) 23
		#define db(...) 23
		#define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

variant <bool, vector <int>> find_journey(int N, int M, vector <int> U, vector <int> V) {
	vector <set <int>> adj(N), radj(N);
	REP(i, M) {
		adj[U[i]].insert(i);
		radj[V[i]].insert(i);
	}
	queue <int> q;
	REP(i, N) if (adj[i].empty()) q.push(i);

	int u = 0;
	vector <int> path;
	while (true) {
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int id: radj[u]) {
				adj[U[id]].erase(id);
				if (adj[U[id]].empty()) q.push(U[id]);
			}
			radj[u].clear();
		}
		if (adj[u].empty()) return false;
		if (adj[u].size() == 1) {
			int id = *adj[u].begin();
			int v = V[id];
			path.push_back(id);
			adj[u].erase(id);
			radj[v].erase(id);
			q.push(u);
			u = v;
			continue;
		}
		REP(i, N) while (adj[i].size() > 1 + (i == u)) adj[i].erase(adj[i].begin());
		int cnt_1 = 0;
		vector <int> states(M), cycle;
		do {
			int id = *adj[u].begin();
			adj[u].erase(id);
			if (!cycle.empty()) adj[u].insert(cycle.back());
			cycle.push_back(id);
			u = U[id] ^ V[id] ^ u;
			states[id] ^= 1;
			cnt_1 += states[id] ? 1 : -1;
		} while (cnt_1);
		vector <int> res = path;
		res.insert(res.end(), ALL(cycle));
		res.insert(res.end(), path.rbegin(), path.rend());
		return res;
	}
	return false;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	100 ms	23780 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	123 ms	19492 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	852 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	432 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	568 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	296 KB	Output is correct
16	Correct	1 ms	304 KB	Output is correct
17	Correct	59 ms	12496 KB	Output is correct
18	Correct	52 ms	10008 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	0 ms	304 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	103 ms	19536 KB	Output is correct

Subtask #4

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	122 ms	21684 KB	Output is correct
4	Correct	124 ms	22080 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	2 ms	852 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct
13	Correct	2 ms	952 KB	Output is correct
14	Correct	2 ms	852 KB	Output is correct
15	Correct	2 ms	1108 KB	Output is correct
16	Correct	2 ms	596 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct
19	Correct	1 ms	596 KB	Output is correct
20	Correct	144 ms	23356 KB	Output is correct
21	Correct	121 ms	22148 KB	Output is correct
22	Correct	1 ms	564 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	276 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	135 ms	23236 KB	Output is correct
28	Correct	129 ms	23284 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	164 ms	23748 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	136 ms	22184 KB	Output is correct
33	Correct	131 ms	22920 KB	Output is correct
34	Correct	66 ms	12492 KB	Output is correct
35	Correct	1 ms	468 KB	Output is correct
36	Correct	112 ms	19660 KB	Output is correct
37	Correct	121 ms	23304 KB	Output is correct
38	Correct	1 ms	468 KB	Output is correct
39	Correct	106 ms	18264 KB	Output is correct
40	Correct	1 ms	596 KB	Output is correct
41	Correct	154 ms	23808 KB	Output is correct
42	Correct	124 ms	23284 KB	Output is correct
43	Correct	1 ms	212 KB	Output is correct
44	Correct	3 ms	852 KB	Output is correct
45	Correct	1 ms	564 KB	Output is correct
46	Correct	34 ms	10060 KB	Output is correct

Subtask #5

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	100 ms	23780 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	123 ms	19492 KB	Output is correct
14	Correct	2 ms	852 KB	Output is correct
15	Correct	1 ms	296 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	596 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	432 KB	Output is correct
21	Correct	1 ms	304 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	568 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	596 KB	Output is correct
26	Correct	1 ms	300 KB	Output is correct
27	Correct	1 ms	300 KB	Output is correct
28	Correct	1 ms	296 KB	Output is correct
29	Correct	1 ms	304 KB	Output is correct
30	Correct	59 ms	12496 KB	Output is correct
31	Correct	52 ms	10008 KB	Output is correct
32	Correct	1 ms	300 KB	Output is correct
33	Correct	0 ms	304 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	103 ms	19536 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	61 ms	10444 KB	Output is correct
42	Correct	3 ms	980 KB	Output is correct
43	Correct	62 ms	17068 KB	Output is correct
44	Correct	61 ms	17072 KB	Output is correct
45	Correct	114 ms	17100 KB	Output is correct
46	Correct	1 ms	212 KB	Output is correct
47	Correct	1 ms	212 KB	Output is correct
48	Correct	0 ms	300 KB	Output is correct
49	Correct	1 ms	556 KB	Output is correct
50	Correct	108 ms	25528 KB	Output is correct
51	Correct	174 ms	33484 KB	Output is correct
52	Correct	186 ms	33516 KB	Output is correct
53	Correct	183 ms	34292 KB	Output is correct
54	Correct	187 ms	33852 KB	Output is correct
55	Correct	182 ms	33932 KB	Output is correct
56	Correct	181 ms	33936 KB	Output is correct
57	Correct	118 ms	30764 KB	Output is correct
58	Correct	146 ms	25536 KB	Output is correct
59	Correct	186 ms	34048 KB	Output is correct
60	Correct	235 ms	34068 KB	Output is correct
61	Correct	196 ms	33936 KB	Output is correct
62	Correct	18 ms	8452 KB	Output is correct
63	Correct	158 ms	32668 KB	Output is correct
64	Correct	76 ms	12696 KB	Output is correct
65	Correct	1 ms	296 KB	Output is correct
66	Correct	1 ms	340 KB	Output is correct
67	Correct	167 ms	34760 KB	Output is correct
68	Correct	259 ms	23832 KB	Output is correct
69	Correct	86 ms	21968 KB	Output is correct
70	Correct	1 ms	596 KB	Output is correct
71	Correct	156 ms	23172 KB	Output is correct
72	Correct	1 ms	212 KB	Output is correct
73	Correct	193 ms	31152 KB	Output is correct
74	Correct	126 ms	24976 KB	Output is correct
75	Correct	5 ms	1620 KB	Output is correct
76	Correct	35 ms	12248 KB	Output is correct
77	Correct	87 ms	21832 KB	Output is correct
78	Correct	223 ms	34060 KB	Output is correct
79	Correct	1 ms	212 KB	Output is correct
80	Correct	256 ms	36520 KB	Output is correct
81	Correct	1 ms	564 KB	Output is correct
82	Correct	168 ms	23004 KB	Output is correct
83	Correct	1 ms	468 KB	Output is correct
84	Correct	1 ms	212 KB	Output is correct
85	Correct	57 ms	12592 KB	Output is correct
86	Correct	1 ms	724 KB	Output is correct
87	Correct	5 ms	8272 KB	Output is correct
88	Correct	2 ms	1076 KB	Output is correct
89	Correct	184 ms	34072 KB	Output is correct
90	Correct	215 ms	34036 KB	Output is correct
91	Correct	201 ms	36016 KB	Output is correct
92	Correct	1 ms	212 KB	Output is correct