Submission #730265

#TimeUsernameProblemLanguageResultExecution timeMemory
730265Nahian9696Thousands Islands (IOI22_islands)C++17
31 / 100
33 ms6968 KiB
#include "islands.h" #include <variant> #include <vector> #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define f0(i, n) for(int i = 0; i < (n); i++) #define f1(i, n) for(int i = 1; i <= (n); i++) #define ff first #define ss second #define pb push_back int opp(int n) { if(n % 2 == 0) return n+1; return n-1; } int viss[20005] = {0}; pair<bool, int> bfs(int u, int par, vi &cur, vector<pair<int, int>> grph[]) { cur.pb(u); for(auto nxt: grph[u]) { if(nxt.ff == par) continue; if(viss[nxt.ff]) { int n = cur.size(); f0(i, n) if(cur[i] == nxt.ff) return {1, i}; } viss[nxt.ff] = true; auto pp = bfs(nxt.ff, u, cur, grph); if(pp.ff) return pp; } cur.pop_back(); return {0, -1}; } std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) { if(N == 2) { vi zr, on; f0(i, M) { if(U[i] == 0) zr.pb(i); else on.pb(i); } if(zr.size() < 2 || on.size() < 1) return false; return vi({zr[0], on[0], zr[1], zr[0], on[0], zr[1]}); } bool sbtsk3 = (M % 2 == 0); bool sbtsk4 = (M % 2 == 0); f0(i, M - 1) { if(i % 2 == 0) { if(U[i] != V[i+1] || V[i] != U[i+1]) { sbtsk3 = false; } if(U[i] != U[i+1] || V[i] != V[i+1]) { sbtsk4 = false; } } } if(sbtsk3) { vector<pair<int, int>> grph[N]; bool vis[N] = {0}; f0(i, M) { grph[U[i]].pb({V[i], i}); } vi ans, t_ans; int cur = 0; vis[cur] = true; if(grph[cur].size() > 1) { int x = grph[cur][0].ss, y = grph[cur][1].ss; return vi({x, opp(x), y, opp(y), opp(x), x, opp(y), y}); } else if (grph[cur].size() == 0) { return false; } else { ans.pb(grph[cur][0].ss); cur = grph[cur][0].ff; } vis[cur] = true; while(grph[cur].size() <= 2) { if(grph[cur].size() == 1) return false; for(auto nxt: grph[cur]) { if(!vis[nxt.ff]) { ans.pb(nxt.ss); cur = nxt.ff; vis[cur] = true; } } } for(auto nxt: grph[cur]) { if(!vis[nxt.ff]) { t_ans.pb(nxt.ss); } } int x = t_ans[0], y = t_ans[1]; t_ans.clear(); t_ans = vi(ans.rbegin(), ans.rend()); ans.pb(x); ans.pb(opp(x)); ans.pb(y); ans.pb(opp(y)); ans.pb(opp(x)); ans.pb(x); ans.pb(opp(y)); ans.pb(y); for(int e: t_ans) ans.pb(e); return ans; } int mat[N][N]; f0(i, M) { mat[U[i]][V[i]] = i; } vi ans; ans.pb(mat[0][1]); ans.pb(mat[1][0]); ans.pb(mat[0][2]); ans.pb(mat[2][0]); ans.pb(mat[1][0]); ans.pb(mat[0][1]); ans.pb(mat[2][0]); ans.pb(mat[0][2]); return ans; if(sbtsk4) { vector<pair<int, int>> grph[N]; // bool vis[N] = {0}; int mat[N][N]; f0(i, M) { if(i % 2 == 0) { grph[U[i]].pb({V[i], i}); mat[U[i]][V[i]] = i; } } vi cur; viss[0] = true; auto pp = bfs(0, -1, cur, grph); if(pp.ff) { vi ans, t_ans, t_t_ans; int k = pp.ss, n = cur.size(); // cout << k << endl; f0(i, k) { ans.pb(mat[cur[i]][cur[i+1]]); } t_ans = vi(ans.rbegin(), ans.rend()); for(int i = k; i < (n-1); i++) { t_t_ans.pb(mat[cur[i]][cur[i+1]]); } t_t_ans.pb(mat[cur[n-1]][cur[k]]); for(int p: t_t_ans) { ans.pb(p); } for(int p: t_t_ans) { ans.pb(opp(p)); // cout << p << " "; } // cout << endl; t_t_ans = vi(t_t_ans.rbegin(), t_t_ans.rend()); for(int p: t_t_ans) { ans.pb(p); } for(int p: t_t_ans) { ans.pb(opp(p)); } for(int p: t_ans) { ans.pb(p); } return ans; } return false; } if (N == 4) { return std::vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3}); } return false; }
#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...