제출 #830684

#제출 시각아이디문제언어결과실행 시간메모리
830684FatihSolak수천개의 섬 (IOI22_islands)C++17
31 / 100
115 ms27220 KiB
#include "islands.h" #include <bits/stdc++.h> #define N 100005 using namespace std; vector<pair<int,pair<int,int>>> adj[N]; map<int,vector<int>> mp[N]; int par[N]; int par2[N]; int vis[N]; vector<int> ans; void dfs(int v,int pr){ vis[v] = 1; vector<pair<int,pair<int,int>>> tmp; for(auto u:adj[v]){ if(ans.size()) return; if(u.second.second == pr) continue; if(vis[u.first] == 2) continue; tmp.push_back(u); } if(tmp.size() > 1){ int now = v; while(now != 0){ ans.push_back(par[now]); now = par2[now]; } reverse(ans.begin(),ans.end()); ans.push_back(tmp[0].second.first); ans.push_back(tmp[0].second.second); ans.push_back(tmp[1].second.first); ans.push_back(tmp[1].second.second); ans.push_back(tmp[0].second.second); ans.push_back(tmp[0].second.first); ans.push_back(tmp[1].second.second); ans.push_back(tmp[1].second.first); now = v; while(now != 0){ ans.push_back(par[now]); now = par2[now]; } return; } else{ for(auto u:adj[v]){ if(ans.size()) return; if(vis[u.first]) continue; par[u.first] = u.second.first; par2[u.first] = v; dfs(u.first,u.second.first); } } vis[v] = 2; } void dfs2(int v,int pr){ vis[v] = 1; vector<pair<int,pair<int,int>>> tmp; for(auto u:adj[v]){ if(ans.size()) return; if(vis[u.first] == 2){ ans.push_back(0); return; } if(vis[u.first] == 1) continue; par[u.first] = u.second.first; par2[u.first] = v; dfs2(u.first,u.second.first); } vis[v] = 2; } variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V){ if(n == 2){ for(int i = 0;i<m;i++){ mp[U[i]][V[i]].push_back(i); } if(mp[0][1].size() < 2 || mp[1][0].size() < 1) return false; int a = mp[0][1][0]; int b = mp[0][1][1]; int c = mp[1][0][0]; ans = {a,c,b,a,c,b}; return ans; } bool subtask4 = (m + 1)%2; for(int i = 0;i<m && subtask4;i+=2){ if(U[i] != U[i+1] || V[i] != V[i+1]) subtask4 = 0; } if(subtask4){ for(int i = 0;i<m;i++){ adj[U[i]].push_back({V[i],{i,i+1}}); } dfs2(0,-1); return ans.empty(); } for(int i = 0;i<m;i++){ if(mp[V[i]][U[i]].size()){ adj[U[i]].push_back({V[i],{i,mp[V[i]][U[i]].back()}}); adj[V[i]].push_back({U[i],{mp[V[i]][U[i]].back(),i}}); mp[V[i]][U[i]].pop_back(); }else{ mp[U[i]][V[i]].push_back(i); } } dfs(0,-1); if(ans.empty()) return false; return ans; }
#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...