제출 #1064349

#제출 시각아이디문제언어결과실행 시간메모리
1064349RaresFelix수천개의 섬 (IOI22_islands)C++17
100 / 100
184 ms36436 KiB
#include "islands.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; void validate(vi Sol, int n, int m, vi &U, vi &V) { int u = 0; vi stare(m, 0); assert(!Sol.empty()); for(int i = 0; i + 1 < int(Sol.size()); ++i) assert(Sol[i] != Sol[i + 1]); for(auto it : Sol) { if(!stare[it]) { assert(u == U[it]); } else { assert(u == V[it]); } stare[it] ^= 1; assert(u == U[it] || u == V[it]); u = u ^ U[it] ^ V[it]; } assert(u == 0); for(int i = 0; i < m; ++i) assert(!stare[i]); } vi solve(int n, int s, vector<ii> &b, vector<ii> &ToGo) { ToGo[s] = b[0]; vector<ii> S; vi viz(n, 0); int v = s; while(!viz[v]) { viz[v] = 1; auto [urm, id] = ToGo[v]; assert(urm != -1); S.push_back(ToGo[v]); v = urm; } vi apartine_c0(n, 0); vi C0; apartine_c0[v] = 1; C0.push_back(S.back().second); S.pop_back(); while(!S.empty() && S.back().first != v) { apartine_c0[S.back().first] = 1; C0.push_back(S.back().second); S.pop_back(); } reverse(C0.begin(), C0.end()); vi A0; for(auto [v_other, id] : S) A0.push_back(id); S.clear(); viz.assign(n, 0); v = b[1].first; S.push_back(b[1]); while(!viz[v] && !apartine_c0[v]) { viz[v] = 1; auto [urm, id] = ToGo[v]; assert(urm != -1); S.push_back(ToGo[v]); v = urm; } if(apartine_c0[v]) { ///ai ajuns in c0 vi A1; for(auto [v_other, id] : S) A1.push_back(id); S.clear(); vi C1; while(!viz[v]) { viz[v] = 1; auto [urm, id] = ToGo[v]; assert(urm != -1); C1.push_back(id); v = urm; } vi Sol; copy(A0.begin(), A0.end(), back_inserter(Sol)); copy(C0.begin(), C0.end(), back_inserter(Sol)); copy(A0.rbegin(), A0.rend(), back_inserter(Sol)); copy(A1.begin(), A1.end(), back_inserter(Sol)); copy(C1.rbegin(), C1.rend(), back_inserter(Sol)); copy(A1.rbegin(), A1.rend(), back_inserter(Sol)); return Sol; } else { ///ai gasit un alt ciclu vi C1; C1.push_back(S.back().second); S.pop_back(); while(!S.empty() && S.back().first != v) { apartine_c0[S.back().first] = 1; C1.push_back(S.back().second); S.pop_back(); } vi A1; reverse(C1.begin(), C1.end()); for(auto [v_other, id] : S) A1.push_back(id); S.clear(); vi Sol; copy(A0.begin(), A0.end(), back_inserter(Sol)); copy(C0.begin(), C0.end(), back_inserter(Sol)); copy(A0.rbegin(), A0.rend(), back_inserter(Sol)); copy(A1.begin(), A1.end(), back_inserter(Sol)); copy(C1.begin(), C1.end(), back_inserter(Sol)); copy(A1.rbegin(), A1.rend(), back_inserter(Sol)); copy(A0.begin(), A0.end(), back_inserter(Sol)); copy(C0.rbegin(), C0.rend(), back_inserter(Sol)); copy(A0.rbegin(), A0.rend(), back_inserter(Sol)); copy(A1.begin(), A1.end(), back_inserter(Sol)); copy(C1.rbegin(), C1.rend(), back_inserter(Sol)); copy(A1.rbegin(), A1.rend(), back_inserter(Sol)); return Sol; } } variant<bool, vi> find_journey(int n, int m, vi U, vi V) { vector<set<ii> > Smuchii(n), Smuchii2(n); vector<bool> activ(n, true); vi InDeg(n, 0), OutDeg(n, 0); for(int i = 0; i < m; ++i) { Smuchii[U[i]].insert({V[i], i}); Smuchii2[V[i]].insert({U[i], i}); ++OutDeg[U[i]]; ++InDeg[V[i]]; } set<int> DeSters; for(int i = 0; i < n; ++i) { if((!InDeg[i] && i != 0) || !OutDeg[i]) { DeSters.insert(i); } } auto dezactiveaza = [&](int u) { DeSters.erase(u); activ[u] = false; for(auto [it, id] : Smuchii[u]) { --InDeg[it]; Smuchii2[it].erase({u, id}); if(!InDeg[it] && activ[it]) { DeSters.insert(it); } } for(auto [it, id] : Smuchii2[u]) { --OutDeg[it]; Smuchii[it].erase({u, id}); if(!OutDeg[it] && activ[it]) { DeSters.insert(it); } } Smuchii[u].clear(); Smuchii2[u].clear(); OutDeg[u] = InDeg[u] = 0; }; int s = 0; while(!DeSters.empty()) { int u = *DeSters.begin(); if(u == s && OutDeg[u]) { DeSters.erase(u); continue; } dezactiveaza(u); } if(!activ[0]) return false; vi Start; while(OutDeg[s] == 1) { activ[s] = 0; auto [ult, ultm] = *Smuchii[s].begin(); --OutDeg[s]; --InDeg[ult]; dezactiveaza(s); s = ult; if(!activ[s]) return false; Start.push_back(ultm); while(!DeSters.empty()) { int u = *DeSters.begin(); if(u == s && OutDeg[u]) { DeSters.erase(u); continue; } dezactiveaza(u); } } if(!activ[s] || OutDeg[s] < 2) return false; vector<ii> ToGo(n, ii{-1, -1}); vector<ii> b; for(int i = 0; i < m; ++i) { int u = U[i], v = V[i]; if(!activ[u] || !activ[v] || ToGo[u].second != -1) continue; if(u != s) { ToGo[u] = {v, i}; } else { b.push_back({v, i}); } } assert(b.size() == Smuchii[s].size()); auto Sol0 = solve(n, s, b, ToGo); vi Sol; copy(Start.begin(), Start.end(), back_inserter(Sol)); copy(Sol0.begin(), Sol0.end(), back_inserter(Sol)); copy(Start.rbegin(), Start.rend(), back_inserter(Sol)); // validate(Sol, n, m, U, V); return Sol; }
#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...