제출 #837429

#제출 시각아이디문제언어결과실행 시간메모리
837429ymm수천개의 섬 (IOI22_islands)C++17
9.10 / 100
1082 ms7740 KiB
#include "islands.h" #include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++x) typedef long long ll; using namespace std; const int N = 100'010; int height[N], mnup[N], mxup[N]; vector<int> A[N]; bool vis[N]; bool anc[N]; int mncnt[N]; int kooft[N]; int par[N]; int marg[N]; int mark[N]; int mark2[N]; bool good[N]; bool dfs1(int v, int p, int h) { par[v] = p; vis[v] = 1; anc[v] = 1; height[v] = h; mnup[v] = N; mxup[v] = -N; int cnt = 0; for (int u : A[v]) { if (anc[u]) { mnup[v] = min(mnup[v], height[u]); mxup[v] = max(mxup[v], height[u]); kooft[u]--; marg[u]++; mark2[v] = 1; } if (vis[u]) { if (par[u] == v) good[u] = 1; continue; } auto tmp = dfs1(u, v, h+1); cnt += !!marg[v] || tmp; mark[u] = !!marg[v]; marg[v] = 0; mnup[v] = min(mnup[v], mnup[u]); if (mxup[u] <= height[v]) mxup[v] = max(mxup[v], mxup[u]); mark2[v] |= mark2[u]; } if (cnt >= 2) throw 1; anc[v] = 0; return cnt; } void dfs2(int v, int mx) { mx = max(mxup[v], mx); mxup[v] = mx; for (int u : A[v]) { if (par[u] != v) continue; dfs2(u, mx); } } bool has_back(int v) { return mnup[v] <= height[v]; } void make_count() { vector<int> vec = {0}; fill(mncnt, mncnt+N, N); mncnt[0] = -1; while (vec.size()) { int v = vec.back(); vec.pop_back(); vis[v] = 1; int x = has_back(v)? height[v]: mncnt[v]; for (int u : A[v]) { if (!vis[u]) { mncnt[u] = min(mncnt[u], x); if (!--kooft[u]) vec.push_back(u); } } } } std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) { Loop (i,0,M) { A[U[i]].push_back(V[i]); kooft[V[i]]++; } try { dfs1(0, -1, 0); } catch(int) { return true; } dfs2(0, -N); Loop (i,0,N) { if (vis[i]) continue; for (int u : A[i]) kooft[u]--; } memset(vis, 0, sizeof(vis)); make_count(); Loop (i,0,N) { if (has_back(i) && mncnt[i] <= mxup[i] && (mncnt[i] < height[i]-1 || good[i])) return true; } 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...