#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= ll(l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
namespace s1 {
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
vector<int> v[2];
Loop (i,0,M)
v[U[i]].push_back(i);
if (v[0].size() < 2 || v[1].size() < 1)
return false;
vector<int> ans = {
v[0][0], v[1][0], v[0][1], v[0][0], v[1][0], v[0][1],
};
return ans;
}
}
namespace s2 {
const int N = 512;
int a[N][N];
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
if (N == 2)
return false;
Loop (i,0,M)
a[U[i]][V[i]] = i;
vector<int> ans = {
a[0][1], a[1][0], a[0][2], a[2][0], a[1][0], a[0][1], a[2][0], a[0][2],
};
return ans;
}
}
namespace s3 {
const int N = 100'010;
vector<pii> A[N];
bool vis[N];
bool anc[N];
vector<int> ans;
void answer(int v, int p)
{
vector<int> vec;
for (auto [u, e] : A[v]) {
if (u == p)
continue;
vec.push_back(e);
}
vector<int> tmp = ans;
ans.push_back(vec[0]^0);
ans.push_back(vec[0]^1);
ans.push_back(vec[1]^0);
ans.push_back(vec[1]^1);
ans.push_back(vec[0]^1);
ans.push_back(vec[0]^0);
ans.push_back(vec[1]^1);
ans.push_back(vec[1]^0);
reverse(tmp.begin(), tmp.end());
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
bool dfs(int v, int p)
{
if (A[v].size() - (p != -1) >= 2) {
answer(v, p);
return 1;
}
for (auto [u, e] : A[v]) {
if (u == p)
continue;
ans.push_back(e);
if (dfs(u, v))
return 1;
ans.pop_back();
}
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
Loop (i,0,M)
A[U[i]].push_back({V[i], i});
if (!dfs(0, -1))
return false;
return ans;
}
}
namespace s4 {
const int N = 100'010;
vector<pii> A[N];
bool vis[N];
bool anc[N];
int height[N];
vector<int> ans;
void answer(int v, int u, int e)
{
ans.push_back(e);
int cnt = height[u] - height[v] + 1;
int pre = ans.size() - cnt;
Loop (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
LoopR (i,pre,pre+cnt)
ans.push_back(ans[i]^0);
LoopR (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
LoopR (i,0,pre)
ans.push_back(ans[i]);
}
bool dfs(int v, int h)
{
height[v] = h;
vis[v] = 1;
anc[v] = 1;
for (auto [u, e] : A[v]) {
if (anc[u]) {
answer(u, v, e);
return 1;
}
if (vis[u])
continue;
ans.push_back(e);
if (dfs(u, h+1))
return 1;
ans.pop_back();
}
anc[v] = 0;
return 0;
}
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 += 2)
A[U[i]].push_back({V[i], i});
if (!dfs(0, 0))
return false;
return ans;
}
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
if (N == 2)
return s1::find_journey(N, M, U, V);
bool is3 = M%2 == 0;
for (int i = 0; i+2 <= M; i += 2)
is3 &= U[i] == V[i+1] && U[i+1] == V[i];
if (is3)
return s3::find_journey(N, M, U, V);
bool is4 = M%2 == 0;
for (int i = 0; i+2 <= M; i += 2)
is4 &= U[i] == U[i+1] && V[i+1] == V[i];
if (is4)
return s4::find_journey(N, M, U, V);
return s2::find_journey(N, M, U, V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
28 ms |
10688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
30 ms |
10616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5012 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4996 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5076 KB |
Output is correct |
11 |
Correct |
2 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
2 ms |
4892 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
18 ms |
8532 KB |
Output is correct |
18 |
Correct |
16 ms |
8020 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
2 ms |
4948 KB |
Output is correct |
21 |
Correct |
2 ms |
4948 KB |
Output is correct |
22 |
Correct |
2 ms |
4948 KB |
Output is correct |
23 |
Correct |
28 ms |
10572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
27 ms |
10196 KB |
Output is correct |
4 |
Correct |
29 ms |
10324 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5204 KB |
Output is correct |
11 |
Correct |
3 ms |
5204 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5204 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5204 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5076 KB |
Output is correct |
20 |
Correct |
29 ms |
10828 KB |
Output is correct |
21 |
Correct |
29 ms |
10216 KB |
Output is correct |
22 |
Correct |
4 ms |
5204 KB |
Output is correct |
23 |
Correct |
3 ms |
4948 KB |
Output is correct |
24 |
Correct |
2 ms |
4948 KB |
Output is correct |
25 |
Correct |
4 ms |
5076 KB |
Output is correct |
26 |
Correct |
3 ms |
5204 KB |
Output is correct |
27 |
Correct |
45 ms |
10724 KB |
Output is correct |
28 |
Correct |
30 ms |
10700 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Correct |
31 ms |
11084 KB |
Output is correct |
31 |
Correct |
2 ms |
4948 KB |
Output is correct |
32 |
Correct |
28 ms |
10572 KB |
Output is correct |
33 |
Correct |
28 ms |
10612 KB |
Output is correct |
34 |
Correct |
16 ms |
7892 KB |
Output is correct |
35 |
Correct |
2 ms |
5076 KB |
Output is correct |
36 |
Correct |
26 ms |
9804 KB |
Output is correct |
37 |
Correct |
37 ms |
10732 KB |
Output is correct |
38 |
Correct |
3 ms |
5076 KB |
Output is correct |
39 |
Correct |
29 ms |
9692 KB |
Output is correct |
40 |
Correct |
3 ms |
5076 KB |
Output is correct |
41 |
Correct |
33 ms |
11056 KB |
Output is correct |
42 |
Correct |
31 ms |
10648 KB |
Output is correct |
43 |
Correct |
2 ms |
4948 KB |
Output is correct |
44 |
Correct |
3 ms |
5076 KB |
Output is correct |
45 |
Correct |
4 ms |
5204 KB |
Output is correct |
46 |
Correct |
16 ms |
7452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
28 ms |
10688 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
4948 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
30 ms |
10616 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5012 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
2 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4996 KB |
Output is correct |
21 |
Correct |
2 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
2 ms |
4948 KB |
Output is correct |
25 |
Correct |
3 ms |
5076 KB |
Output is correct |
26 |
Correct |
2 ms |
4892 KB |
Output is correct |
27 |
Correct |
2 ms |
4948 KB |
Output is correct |
28 |
Correct |
2 ms |
4948 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Correct |
18 ms |
8532 KB |
Output is correct |
31 |
Correct |
16 ms |
8020 KB |
Output is correct |
32 |
Correct |
3 ms |
4948 KB |
Output is correct |
33 |
Correct |
2 ms |
4948 KB |
Output is correct |
34 |
Correct |
2 ms |
4948 KB |
Output is correct |
35 |
Correct |
2 ms |
4948 KB |
Output is correct |
36 |
Correct |
28 ms |
10572 KB |
Output is correct |
37 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
38 |
Correct |
2 ms |
4948 KB |
Output is correct |
39 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |