제출 #628452

#제출 시각아이디문제언어결과실행 시간메모리
628452peti1234수천개의 섬 (IOI22_islands)C++17
10 / 100
137 ms15328 KiB
#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]; 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) { // a-b es b-d a ket specialis el, b es d nek nagyobb a szintje if (kesz) return; 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()); for (auto p:sz[b]) { bool jo=0; 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()); for (auto p:sz[d]) { bool jo=0; 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() { assert(!kesz); kesz=1; int pos=jobb[ut2.back()]; assert(korben[pos]); // alaput, alapkor, ut2, pos 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(); } } } 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; } 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) { return false; } else { ans=valt(ans); assert(ans.size()>0); return ans; //return true; } /*if (N > 2) { return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3}); } return false;*/ } /* 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 ans=find_journey(nn, mm, aa, bb); cout << "sikerult: " << ans << "\n"; return 0; } */ /* 2 3 0 1 1 0 1 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...