Submission #994307

#TimeUsernameProblemLanguageResultExecution timeMemory
994307Error42Jail (JOI22_jail)C++17
61 / 100
5054 ms495640 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; vector<vector<int>> graph; vector<int> cur_path; bool dfs(int const cur, int const par, int const goal) { if (cur == goal) { cur_path.push_back(cur); return true; } for (int const& neigh : graph[cur]) { if (neigh == par) continue; if (dfs(neigh, cur, goal)) { cur_path.push_back(cur); return true; } } return false; } bool solve() { int n; cin >> n; graph.assign(n, {}); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; graph[u].push_back(v); graph[v].push_back(u); } int m; cin >> m; vector<int> start(m); vector<int> end(m); vector<int> end_of(n, -1); vector<vector<int>> path(m); for (int i = 0; i < m; i++) { cin >> start[i] >> end[i]; start[i]--; end[i]--; end_of[end[i]] = i; cur_path.clear(); dfs(start[i], -1, end[i]); path[i] = move(cur_path); } vector<char> ended(m); vector<int> violations(m); vector<vector<int>> in_path(n); for (int i = 0; i < m; i++) { for (int const& v : path[i]) in_path[v].push_back(i); } for (int i = 0; i < m; i++) { for (int const& j : in_path[start[i]]) violations[j]++; for (int const& j : in_path[end[i]]) violations[i]++; } vector<int> available; for (int i = 0; i < m; i++) { if (violations[i] == 2) available.push_back(i); } for (int iter = 0; iter < m; iter++) { if (available.size() == 0) return false; int const i = available.back(); available.pop_back(); for (int const& j : in_path[start[i]]) { violations[j]--; if (violations[j] == 2) available.push_back(j); } for (int const& v : path[i]) { if (end_of[v] == -1) continue; violations[end_of[v]]--; if (violations[end_of[v]] == 2) { available.push_back(end_of[v]); } } ended[i] = true; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) cout << (solve() ? "Yes\n" : "No\n"); }

Compilation message (stderr)

jail.cpp: In function 'bool solve()':
jail.cpp:77:25: warning: unused variable 'j' [-Wunused-variable]
   77 |         for (int const& j : in_path[end[i]])
      |                         ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...