제출 #722673

#제출 시각아이디문제언어결과실행 시간메모리
722673bin9638수천개의 섬 (IOI22_islands)C++17
8.40 / 100
56 ms12320 KiB
#include <bits/stdc++.h> #ifndef SKY #include "islands.h" #endif // SKY using namespace std; #define N 100010 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back int sz[N],n,m,ktr[N],ans=0,pos[N],num[N],low[N],times,dem; vector<int>g[N],edge[N]; stack<int>st; void visit(int u) { num[u]=low[u]=++times; st.push(u); for(auto v:g[u]) if(num[v]!=0) { low[u]=min(low[u],num[v]); }else { visit(v); low[u]=min(low[u],low[v]); } if(low[u]==num[u]) { int k; dem++; do{ k=st.top(); st.pop(); num[k]=low[k]=1e9; pos[k]=dem; sz[dem]++; }while(k!=u); } } void DFS(int u) { ktr[u]=1; if(sz[u]>=2) ans=1; for(auto v:edge[u]) if(ktr[v]==0) DFS(v); } #ifdef SKY vector<int> #endif // SKY #ifndef SKY variant<bool, vector<int>> #endif // SKY find_journey(int NNN, int MMM, vector<int> canh_fs, vector<int> canh_sc) { n=NNN; m=MMM; for(int i=0;i<m;i++) { int u=canh_fs[i],v=canh_sc[i]; g[u].pb(v); } for(int i=0;i<n;i++) if(num[i]==0) visit(i); for(int i=0;i<m;i++) { int u=canh_fs[i],v=canh_sc[i]; if(pos[u]!=pos[v]) edge[pos[u]].pb(pos[v]); } DFS(pos[0]); #ifdef SKY return{ans}; #endif // SKY #ifndef SKY return (ans==1); #endif // SKY } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); return 0; } #endif
#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...