Submission #401885

#TimeUsernameProblemLanguageResultExecution timeMemory
401885timmyfengAmusement Park (JOI17_amusement_park)C++17
100 / 100
35 ms4716 KiB
#include <bits/stdc++.h> using namespace std; #include "Joi.h" const int L = 60; void Joi(int n, int m, int *a, int *b, long long x, int t) { vector<vector<int>> adj(n); for (int i = 0; i < m; ++i) { adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } vector<int> id(n, -1), in(n, -1), out(n, INT_MAX), sub; auto dfs = [&](int u, auto &self) -> void { in[u] = t++; sub.push_back(u); for (auto c : adj[u]) { if (id[c] == -1) { int v = -1; if ((int) sub.size() == L) { v = *min_element(sub.begin(), sub.end(), [&](int a, int b) { if (out[a] == out[b]) { return in[a] < in[b]; } else { return out[a] < out[b]; } } ); sub.erase(find(sub.begin(), sub.end(), v)); id[c] = id[v]; } else { id[c] = sub.size(); } self(c, self); if (v != -1) { sub.erase(find(sub.begin(), sub.end(), c)); sub.push_back(v); } } } out[u] = t++; }; id[0] = 0; dfs(0, dfs); for (int i = 0; i < n; ++i) { MessageBoard(i, (x & (1LL << id[i])) > 0); } }
#include <bits/stdc++.h> using namespace std; #include "Ioi.h" const int L = 60; long long Ioi(int n, int m, int *a, int *b, int p, int v, int t) { vector<vector<int>> adj(n); for (int i = 0; i < m; ++i) { adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } bool found = false; vector<int> id(n, -1), in(n, -1), out(n, INT_MAX), sub; auto dfs_find = [&](int u, auto &self) -> bool { in[u] = t++; found |= u == p; sub.push_back(u); if (found && (int) sub.size() == L) { return true; } for (auto c : adj[u]) { if (id[c] == -1) { int v = -1; if ((int) sub.size() == L) { v = *min_element(sub.begin(), sub.end(), [&](int a, int b) { if (out[a] == out[b]) { return in[a] < in[b]; } else { return out[a] < out[b]; } } ); sub.erase(find(sub.begin(), sub.end(), v)); id[c] = id[v]; } else { id[c] = sub.size(); } if (self(c, self)) { return true; } if (v != -1) { sub.erase(find(sub.begin(), sub.end(), c)); sub.push_back(v); } } } out[u] = t++; return false; }; id[0] = 0; dfs_find(0, dfs_find); long long ans = 0; auto dfs_read = [&](int u, auto &self) -> void { sub.erase(find(sub.begin(), sub.end(), u)); ans |= v * (1LL << id[u]); for (auto c : adj[u]) { if (count(sub.begin(), sub.end(), c) > 0) { v = Move(c); self(c, self); v = Move(u); } } }; dfs_read(p, dfs_read); return ans; }
#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...