제출 #832889

#제출 시각아이디문제언어결과실행 시간메모리
832889Username4132수천개의 섬 (IOI22_islands)C++17
17.50 / 100
1087 ms8696 KiB
#include "islands.h" #include <variant> #include<iostream> #include <vector> using namespace std; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define PB push_back const int MAXN = 100010; int n, m; bool marked[MAXN], inst[MAXN], vis[MAXN]; vector<int> g[MAXN]; vector<int> st; bool dfs1(int v){ vis[v]=inst[v]=true; st.PB(v); bool ret=false; for(int to:g[v]) if(!marked[to] && !vis[to]){ ret|=dfs1(to); } else if(inst[to]){ ret=true; } st.pop_back(); inst[v]=false; return ret; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { n=N, m=M; forn(i, m) g[U[i]].PB(V[i]); int cur=0; while(true){ vector<int> nxt; for(int to:g[cur]) if(!marked[to]){ if(dfs1(to)) nxt.PB(to); forn(i, n) vis[i]=false; } if(nxt.empty()) return false; if((int)nxt.size() > 1){ vector<int> emp; return emp; } marked[cur]=true; cur=nxt.back(); } }
#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...