제출 #1070353

#제출 시각아이디문제언어결과실행 시간메모리
1070353Unforgettablepl수천개의 섬 (IOI22_islands)C++17
22.75 / 100
22 ms6232 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; variant<bool, vector<int>> find_journey(int N,int M,vector<int> U,vector<int> V){ vector<vector<pair<int,int>>> adj(N); for(int i=0;i<M;i++){ adj[U[i]].emplace_back(V[i],i); } vector<bool> visited(N); stack<int> path; vector<int> ans; vector<int> direction; function<int(int,int)> dfs = [&](int x,int pedge) { if(visited[x]) { return x; } visited[x]=true; bool found = false; pair<int,int> idxes = {-1,-1}; for(auto&[v,idx]:adj[x])if(pedge!=idx) { path.emplace(idx); auto temp = dfs(v,idx^1); if(temp==-1){ path.pop(); if(found) { idxes.second=idx; break; } idxes.first=idx; found=true; continue; } if(temp==-2) { direction.emplace_back(idx); return -2; } ans.emplace_back(idx); if(temp!=x) { return temp; } reverse(ans.begin(), ans.end()); vector<int> myans = ans; reverse(ans.begin(), ans.end()); for(int&i:ans)myans.emplace_back(i^1); for(int&i:ans)myans.emplace_back(i); reverse(ans.begin(), ans.end()); for(int&i:ans)myans.emplace_back(i^1); ans = myans; return -2; } if(idxes.second!=-1) { int a = idxes.first; int b = idxes.second; ans = {a,a^1,b,b^1,a^1,a,b^1,b}; return -2; } return -1; }; auto temp = dfs(0,-1); if(temp==-1)return false; reverse(direction.begin(), direction.end()); vector<int> myans = direction; for(int&i:ans)myans.emplace_back(i); reverse(direction.begin(), direction.end()); for(int&i:direction)myans.emplace_back(i); return myans; }
#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...