#include<bits/stdc++.h>
//#include "islands.h"
bool test=0;
using namespace std;
const int c=300005, k=20;
int n, m, szint[c], fel[c], felel[c], fel2[c][k], bal[c], jobb[c], kezd, veg, specid;
vector<int> alaput, alapkor, ans, ut2;
vector<pair<int, int> > sz[c];
bool kesz, v[c], v2[c][2], korben[c], uton[c];
void nullazas() {
for (int i=1; i<=n; i++) {
szint[i]=0, fel[i]=0, felel[i]=0;
v[i]=0, v2[i][0]=0, v2[i][1]=0, korben[i]=0, uton[i]=0;
for (int j=0; j<k; j++) fel2[i][j]=0;
}
alaput.clear(), alapkor.clear(), ans.clear(), ut2.clear();
kezd=0, veg=0, specid=0;
}
int lca(int a, int b) {
if (szint[a]<szint[b]) swap(a, b);
for (int i=k-1; i>=0; i--) {
if (szint[fel2[a][i]]>=szint[b]) a=fel2[a][i];
}
for (int i=k-1; i>=0; i--) {
if (fel2[a][i]!=fel2[b][i]) {
a=fel2[a][i], b=fel2[b][i];
}
}
if (a==b) return a;
return fel2[a][0];
}
void conc(vector<int> & a, vector<int> b) {
for (auto x:b) {
a.push_back(x);
}
}
vector<int> valt(vector<int> a) {
vector<int> b;
for (auto x:a) {
if (b.size()>0 && b.back()==x) b.pop_back();
else b.push_back(x);
}
return b;
}
vector<int> calc(int a, int b) {
assert(lca(a, b)==b);
vector<int> res;
while (a!=b) {
res.push_back(felel[a]);
a=fel[a];
}
return res;
}
void ket_kor(int a, int b, int c, int d) {
if (test) cout << "ket kor\n" << "\n";
// a-b es b-d a ket specialis el, b es d nek nagyobb a szintje
if (kesz) return;
kesz=true;
for (int i=0; i<2; i++) {
vector<int> ut=calc(a, 1);
reverse(ut.begin(), ut.end());
conc(ans, ut);
vector<int> kor=calc(b, a);
reverse(kor.begin(), kor.end());
bool jo=0;
for (auto p:sz[b]) {
if (p.first==a) {
kor.push_back(p.second);
jo=1;
break;
}
}
assert(jo);
if (i==1) reverse(kor.begin(), kor.end());
conc(ans, kor);
reverse(ut.begin(), ut.end());
conc(ans, ut);
ut=calc(c, 1);
reverse(ut.begin(), ut.end());
conc(ans, ut);
kor=calc(d, c);
reverse(kor.begin(), kor.end());
jo=0;
for (auto p:sz[d]) {
if (p.first==c) {
kor.push_back(p.second);
jo=1;
break;
}
}
assert(jo);
if (i==1) reverse(kor.begin(), kor.end());
conc(ans, kor);
reverse(ut.begin(), ut.end());
conc(ans, ut);
}
}
void egy_kor() {
if (test) cout << "egy kor\n";
assert(!kesz);
kesz=1;
int pos=jobb[ut2.back()];
assert(korben[pos]);
// alaput, alapkor, ut2, pos
if (test) {
cout << "alaput: ";
for (auto x:alaput) cout << x << " ";
cout << "\n";
}
conc(ans, alaput);
conc(ans, alapkor);
conc(ans, calc(kezd, 1));
conc(ans, ut2);
int si=alapkor.size(), kezd=-1;
for (int i=0; i<si; i++) {
if (jobb[alapkor[i]]==pos) {
kezd=i;
}
}
assert(kezd!=-1);
for (int i=0; i<si; i++) {
int id=(kezd-i+si)%si;
ans.push_back(alapkor[id]);
}
reverse(ut2.begin(), ut2.end());
conc(ans, ut2);
reverse(ut2.begin(), ut2.end());
}
void dfs(int a) {
if (test) cout << "dfs " << a << "\n";
v[a]=true;
fel2[a][0]=fel[a];
for (int i=1; i<k; i++) {
fel2[a][i]=fel2[fel2[a][i-1]][i-1];
}
for (auto p:sz[a]) {
int x=p.first, y=p.second;
if (test) cout << "fontos " << x << " " << y << "\n";
if (!v[x]) {
szint[x]=szint[a]+1;
fel[x]=a, felel[x]=y;
dfs(x);
} else {
int cs=lca(a, x);
if (cs!=x) continue;
if (kezd==0) {
kezd=x, veg=a, specid=y;
} else {
int s=lca(kezd, x), t=lca(veg, a);
if (s==t) {
ket_kor(kezd, veg, x, a);
} else {
assert(s==kezd || s==x);
if (s==kezd) kezd=x, veg=a, specid=y;
}
}
}
}
}
void dfs2(int a, bool b) {
v2[a][b]=1, uton[a]=1;
if (korben[a] && b && !kesz) {
egy_kor();
}
for (auto p:sz[a]) {
int x=p.first, y=p.second;
if (uton[x]) continue;
int su=alaput.size(), su2=ut2.size();
if (su==su2 && b==0 && y==alapkor[0]) continue;
bool kov=b;
if (su<=su2 || y!=alaput[su2]) kov=1;
if (!v2[x][kov]) {
ut2.push_back(y);
dfs2(x, kov);
assert(ut2.back()==y);
ut2.pop_back();
}
}
uton[a]=0;
}
variant<bool, vector<int>> find_journey(
//bool find_journey(
int N, int M, vector<int> U, vector<int> V) {
n=N, m=M;
for (int i=0; i<m; i++) {
int a=U[i], b=V[i];
sz[a+1].push_back({b+1, i});
bal[i]=a+1, jobb[i]=b+1;
}
for (int proba=0; proba<6; proba++) {
szint[1]=1;
dfs(1);
if (test) cout << "vege " << kezd << " " << veg << "\n";
if (kezd==0) {
return false;
}
alaput=calc(kezd, 1);
reverse(alaput.begin(), alaput.end());
alapkor=calc(veg, kezd);
for (auto x:alapkor) {
korben[bal[x]]=1, korben[jobb[x]]=1;
}
reverse(alapkor.begin(), alapkor.end());
alapkor.push_back(specid);
assert(alapkor.size()>0);
if (!kesz) {
dfs2(1, 0);
}
if (kesz) {
break;
}
nullazas();
for (int i=1; i<=n; i++) {
random_shuffle(sz[i].begin(), sz[i].end());
}
}
if (!kesz) {
return false;
} else {
ans=valt(ans);
assert(ans.size()>0);
return ans;
//return true;
}
}
/*
int main() {
int nn, mm;
vector<int> aa, bb;
cin >> nn >> mm;
for (int i=0; i<mm; i++) {
int x, y;
cin >> x >> y;
aa.push_back(x), bb.push_back(y);
}
bool res=find_journey(nn, mm, aa, bb);
cout << "sikerult: " << res << "\n";
for (auto x:ans) {
cout << x << " ";
}
cout << "\n";
return 0;
}
*/
/*
7
9
0 1 1 2 2 3 3 4 4 5 5 6
4 2
1 5
6 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
6 ms |
7388 KB |
Output is correct |
4 |
Correct |
5 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7380 KB |
Output is correct |
6 |
Correct |
5 ms |
7380 KB |
Output is correct |
7 |
Correct |
120 ms |
13776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
6 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7348 KB |
Output is correct |
6 |
Correct |
102 ms |
13084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7636 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7344 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
9 ms |
7596 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
4 ms |
7380 KB |
Output is correct |
10 |
Correct |
7 ms |
7636 KB |
Output is correct |
11 |
Correct |
4 ms |
7380 KB |
Output is correct |
12 |
Correct |
6 ms |
7636 KB |
Output is correct |
13 |
Correct |
4 ms |
7380 KB |
Output is correct |
14 |
Correct |
4 ms |
7380 KB |
Output is correct |
15 |
Correct |
4 ms |
7380 KB |
Output is correct |
16 |
Correct |
4 ms |
7380 KB |
Output is correct |
17 |
Correct |
64 ms |
11152 KB |
Output is correct |
18 |
Correct |
58 ms |
10664 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7408 KB |
Output is correct |
21 |
Correct |
4 ms |
7380 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
97 ms |
13024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
6 ms |
7508 KB |
Output is correct |
3 |
Correct |
74 ms |
13552 KB |
Output is correct |
4 |
Correct |
72 ms |
13872 KB |
Output is correct |
5 |
Correct |
6 ms |
7636 KB |
Output is correct |
6 |
Correct |
6 ms |
7636 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
6 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7636 KB |
Output is correct |
11 |
Correct |
5 ms |
7644 KB |
Output is correct |
12 |
Correct |
6 ms |
7564 KB |
Output is correct |
13 |
Correct |
6 ms |
7764 KB |
Output is correct |
14 |
Correct |
5 ms |
7636 KB |
Output is correct |
15 |
Correct |
7 ms |
7660 KB |
Output is correct |
16 |
Correct |
5 ms |
7636 KB |
Output is correct |
17 |
Correct |
4 ms |
7380 KB |
Output is correct |
18 |
Correct |
5 ms |
7636 KB |
Output is correct |
19 |
Correct |
5 ms |
7508 KB |
Output is correct |
20 |
Correct |
77 ms |
14384 KB |
Output is correct |
21 |
Correct |
55 ms |
13768 KB |
Output is correct |
22 |
Correct |
5 ms |
7548 KB |
Output is correct |
23 |
Correct |
4 ms |
7380 KB |
Output is correct |
24 |
Correct |
5 ms |
7380 KB |
Output is correct |
25 |
Correct |
5 ms |
7508 KB |
Output is correct |
26 |
Correct |
6 ms |
7636 KB |
Output is correct |
27 |
Correct |
79 ms |
14492 KB |
Output is correct |
28 |
Correct |
82 ms |
14540 KB |
Output is correct |
29 |
Correct |
4 ms |
7380 KB |
Output is correct |
30 |
Correct |
83 ms |
14900 KB |
Output is correct |
31 |
Correct |
4 ms |
7380 KB |
Output is correct |
32 |
Correct |
79 ms |
14408 KB |
Output is correct |
33 |
Correct |
77 ms |
13964 KB |
Output is correct |
34 |
Correct |
63 ms |
11160 KB |
Output is correct |
35 |
Correct |
4 ms |
7508 KB |
Output is correct |
36 |
Correct |
70 ms |
13184 KB |
Output is correct |
37 |
Correct |
78 ms |
14480 KB |
Output is correct |
38 |
Correct |
5 ms |
7508 KB |
Output is correct |
39 |
Correct |
63 ms |
13180 KB |
Output is correct |
40 |
Correct |
5 ms |
7636 KB |
Output is correct |
41 |
Correct |
81 ms |
14868 KB |
Output is correct |
42 |
Correct |
81 ms |
14452 KB |
Output is correct |
43 |
Correct |
4 ms |
7380 KB |
Output is correct |
44 |
Correct |
5 ms |
7636 KB |
Output is correct |
45 |
Correct |
5 ms |
7636 KB |
Output is correct |
46 |
Correct |
52 ms |
10580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
6 ms |
7388 KB |
Output is correct |
4 |
Correct |
5 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7380 KB |
Output is correct |
6 |
Correct |
5 ms |
7380 KB |
Output is correct |
7 |
Correct |
120 ms |
13776 KB |
Output is correct |
8 |
Correct |
5 ms |
7380 KB |
Output is correct |
9 |
Correct |
5 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7380 KB |
Output is correct |
11 |
Correct |
6 ms |
7380 KB |
Output is correct |
12 |
Correct |
5 ms |
7348 KB |
Output is correct |
13 |
Correct |
102 ms |
13084 KB |
Output is correct |
14 |
Correct |
9 ms |
7636 KB |
Output is correct |
15 |
Correct |
4 ms |
7380 KB |
Output is correct |
16 |
Correct |
4 ms |
7344 KB |
Output is correct |
17 |
Correct |
4 ms |
7380 KB |
Output is correct |
18 |
Correct |
9 ms |
7596 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7380 KB |
Output is correct |
21 |
Correct |
4 ms |
7380 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
7 ms |
7636 KB |
Output is correct |
24 |
Correct |
4 ms |
7380 KB |
Output is correct |
25 |
Correct |
6 ms |
7636 KB |
Output is correct |
26 |
Correct |
4 ms |
7380 KB |
Output is correct |
27 |
Correct |
4 ms |
7380 KB |
Output is correct |
28 |
Correct |
4 ms |
7380 KB |
Output is correct |
29 |
Correct |
4 ms |
7380 KB |
Output is correct |
30 |
Correct |
64 ms |
11152 KB |
Output is correct |
31 |
Correct |
58 ms |
10664 KB |
Output is correct |
32 |
Correct |
4 ms |
7380 KB |
Output is correct |
33 |
Correct |
4 ms |
7408 KB |
Output is correct |
34 |
Correct |
4 ms |
7380 KB |
Output is correct |
35 |
Correct |
4 ms |
7380 KB |
Output is correct |
36 |
Correct |
97 ms |
13024 KB |
Output is correct |
37 |
Correct |
4 ms |
7412 KB |
Output is correct |
38 |
Correct |
4 ms |
7380 KB |
Output is correct |
39 |
Correct |
4 ms |
7380 KB |
Output is correct |
40 |
Correct |
6 ms |
7380 KB |
Output is correct |
41 |
Correct |
142 ms |
10588 KB |
Output is correct |
42 |
Correct |
10 ms |
7580 KB |
Output is correct |
43 |
Correct |
231 ms |
21416 KB |
Output is correct |
44 |
Correct |
236 ms |
20932 KB |
Output is correct |
45 |
Correct |
89 ms |
21068 KB |
Output is correct |
46 |
Correct |
4 ms |
7380 KB |
Output is correct |
47 |
Correct |
4 ms |
7380 KB |
Output is correct |
48 |
Correct |
4 ms |
7380 KB |
Output is correct |
49 |
Correct |
4 ms |
7636 KB |
Output is correct |
50 |
Correct |
145 ms |
38592 KB |
Output is correct |
51 |
Correct |
162 ms |
30948 KB |
Output is correct |
52 |
Correct |
688 ms |
33376 KB |
Output is correct |
53 |
Correct |
159 ms |
34820 KB |
Output is correct |
54 |
Correct |
641 ms |
35476 KB |
Output is correct |
55 |
Correct |
710 ms |
34868 KB |
Output is correct |
56 |
Correct |
160 ms |
31448 KB |
Output is correct |
57 |
Correct |
128 ms |
20960 KB |
Output is correct |
58 |
Correct |
126 ms |
31976 KB |
Output is correct |
59 |
Correct |
123 ms |
24396 KB |
Output is correct |
60 |
Correct |
320 ms |
25372 KB |
Output is correct |
61 |
Correct |
56 ms |
15976 KB |
Output is correct |
62 |
Correct |
13 ms |
9020 KB |
Output is correct |
63 |
Correct |
55 ms |
15180 KB |
Output is correct |
64 |
Correct |
45 ms |
11340 KB |
Output is correct |
65 |
Correct |
4 ms |
7380 KB |
Output is correct |
66 |
Correct |
4 ms |
7380 KB |
Output is correct |
67 |
Correct |
165 ms |
28700 KB |
Output is correct |
68 |
Correct |
87 ms |
14828 KB |
Output is correct |
69 |
Correct |
58 ms |
23760 KB |
Output is correct |
70 |
Correct |
5 ms |
7636 KB |
Output is correct |
71 |
Correct |
83 ms |
17760 KB |
Output is correct |
72 |
Correct |
4 ms |
7380 KB |
Output is correct |
73 |
Correct |
112 ms |
21472 KB |
Output is correct |
74 |
Correct |
151 ms |
34156 KB |
Output is correct |
75 |
Correct |
9 ms |
8020 KB |
Output is correct |
76 |
Correct |
58 ms |
19420 KB |
Output is correct |
77 |
Correct |
373 ms |
33036 KB |
Output is correct |
78 |
Correct |
299 ms |
25308 KB |
Output is correct |
79 |
Correct |
4 ms |
7380 KB |
Output is correct |
80 |
Correct |
190 ms |
32476 KB |
Output is correct |
81 |
Correct |
4 ms |
7636 KB |
Output is correct |
82 |
Correct |
80 ms |
13992 KB |
Output is correct |
83 |
Correct |
4 ms |
7508 KB |
Output is correct |
84 |
Correct |
5 ms |
7380 KB |
Output is correct |
85 |
Correct |
49 ms |
18872 KB |
Output is correct |
86 |
Correct |
5 ms |
7636 KB |
Output is correct |
87 |
Correct |
6 ms |
7380 KB |
Output is correct |
88 |
Correct |
6 ms |
7764 KB |
Output is correct |
89 |
Correct |
303 ms |
25292 KB |
Output is correct |
90 |
Correct |
55 ms |
15948 KB |
Output is correct |
91 |
Correct |
203 ms |
30952 KB |
Output is correct |
92 |
Correct |
4 ms |
7380 KB |
Output is correct |