Submission #1037665

#TimeUsernameProblemLanguageResultExecution timeMemory
1037665kunzaZa183Thousands Islands (IOI22_islands)C++17
0 / 100
21 ms6880 KiB
#include <bits/stdc++.h> #include <variant> using namespace std; const int maxn = 10, logm = 4; vector<int> adjlist[maxn]; vector<int> down[maxn], up[maxn]; pair<int, int> arrpii[maxn]; int state[maxn], disc[maxn], depth[maxn]; vector<int> side, extra; int lca[logm][maxn]; int tim = 0, dep = 0; void dfs(int cur) { state[cur] = 1; disc[cur] = tim++; depth[cur] = dep; for (auto a : adjlist[cur]) if (state[arrpii[a].second] == 1) up[cur].push_back(a); else if (state[arrpii[a].second] == 0) { lca[0][arrpii[a].second] = cur; down[cur].push_back(a); dep++; dfs(arrpii[a].second); dep--; } else if (disc[arrpii[a].second] > disc[cur]) extra.push_back(a); else side.push_back(a); state[cur] = 2; } struct cmp { bool operator()(int a, int b) const { return disc[a] > disc[b]; } }; using sidcp = set<int, cmp>*; vector<int> cyc[maxn]; int highdisc[maxn]; sidcp dfs2(int cur) { highdisc[cur] = -1; vector<sidcp> vsd; for (auto a : down[cur]) { vsd.push_back(dfs2(arrpii[a].second)); auto it = vsd.back()->find(cur); if (vsd.back()->count(cur)) { highdisc[cur] = cur; vsd.back()->erase(cur); cyc[cur].push_back(a); } } sidcp maxi = new set<int, cmp>; if (!vsd.empty()) maxi = *max_element(vsd.begin(), vsd.end(), [](sidcp a, sidcp b) { return a->size() < b->size(); }); for (auto a : vsd) if (a != maxi) for (auto b : *a) maxi->insert(b); for (auto a : up[cur]) maxi->insert(arrpii[a].second); if (!maxi->empty()) highdisc[cur] = *maxi->begin(); return maxi; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { for (int i = 0; i < M; i++) { arrpii[i] = { U[i], V[i] }; adjlist[U[i]].push_back(i); } dfs(0); dfs2(0); lca[0][0] = 0; for (int i = 1; i < logm; i++) for (int j = 0; j < N; j++) lca[i][j] = lca[i - 1][lca[i - 1][j]]; for (auto a : extra) { pair<int, int> pii = arrpii[a]; if (highdisc[pii.second] != -1) if (disc[highdisc[pii.second]] >= disc[pii.first]) { return true; // good } } for (auto a : side) { pair<int, int> pii = arrpii[a]; if (highdisc[pii.second] != -1) { int lci; int tmpa = pii.first, tmpb = pii.second; if (depth[tmpa] < depth[tmpb]) { for (int i = logm - 1; i >= 0; i--) if ((1 << i) & (depth[tmpb] - depth[tmpa])) tmpb = lca[i][tmpb]; } else if (depth[tmpa] > depth[tmpb]) { for (int i = logm - 1; i >= 0; i--) if ((1 << i) & (depth[tmpa] - depth[tmpb])) tmpa = lca[i][tmpa]; } for (int i = logm - 1; i >= 0; i--) if (lca[i][tmpa] != lca[i][tmpb]) { tmpa = lca[i][tmpa], tmpb = lca[i][tmpb]; } if (tmpa != tmpb) { tmpa = lca[0][tmpa], tmpb = lca[0][tmpb]; } lci = tmpa; if (disc[lci] <= disc[highdisc[pii.second]]) return true; } } for (int i = 0; i < N; i++) if (cyc[i].size() >= 2) return true; return false; } // int main() { // int N, M; // assert(2 == scanf("%d %d", &N, &M)); // std::vector<int> U(M), V(M); // for (int i = 0; i < M; ++i) { // assert(2 == scanf("%d %d", &U[i], &V[i])); // } // std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V); // if (result.index() == 0) { // printf("0\n"); // if (std::get<bool>(result)) { // printf("1\n"); // } // else { // printf("0\n"); // } // } // else { // printf("1\n"); // std::vector<int>& canoes = std::get<std::vector<int>>(result); // printf("%d\n", static_cast<int>(canoes.size())); // for (int i = 0; i < static_cast<int>(canoes.size()); ++i) { // if (i > 0) { // printf(" "); // } // printf("%d", canoes[i]); // } // printf("\n"); // } // return 0; // }

Compilation message (stderr)

islands.cpp: In function 'std::set<int, cmp>* dfs2(int)':
islands.cpp:51:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   51 |   auto it = vsd.back()->find(cur);
      |        ^~
#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...