Submission #633201

#TimeUsernameProblemLanguageResultExecution timeMemory
633201tutis수천개의 섬 (IOI22_islands)C++17
35 / 100
130 ms15164 KiB
#include "islands.h" #include <variant> #include <vector> #include <bits/stdc++.h> using namespace std; variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { vector<int> C(N, 0); vector<int>b[N]; vector<int>ff[N]; for (int i = 0; i < M; i++) { C[U[i]]++; b[V[i]].push_back(U[i]); ff[U[i]].push_back(i); } int s = 0; vector<bool> e(N, true); stack<int>Q; for (int i = 0; i < N; i++) if (C[i] == 0) Q.push(i); vector<int>ans0; while (e[s]) { if (C[s] == 1) { int s_ = -1; for (int ee : ff[s]) { if (e[V[ee]]) { ans0.push_back(ee); s_ = V[ee]; } } for (int t : b[s]) { if (e[t]) { C[t]--; if (C[t] == 0) Q.push(t); } } e[s] = false; s = s_; continue; } if (Q.empty()) break; int a = Q.top(); Q.pop(); if (!e[a]) continue; e[a] = false; for (int t : b[a]) { if (e[t]) { C[t]--; if (C[t] == 0) Q.push(t); } } } if (!e[s]) return false; return true; }
#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...