제출 #825612

#제출 시각아이디문제언어결과실행 시간메모리
825612t6twotwoTwo Currencies (JOI23_currencies)C++17
10 / 100
5056 ms14660 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector<pair<int, int>> edges(N - 1); vector<vector<pair<int, int>>> adj(N); for (int i = 0; i < N - 1; i++) { int x, y; cin >> x >> y; x--, y--; edges[i] = {x, y}; adj[x].emplace_back(y, i); adj[y].emplace_back(x, i); } vector<vector<int>> c(N - 1); for (int i = 0; i < M; i++) { int P, C; cin >> P >> C; c[P - 1].push_back(C); } while (Q--) { int S, T, X; ll Y; cin >> S >> T >> X >> Y; S--, T--; vector<int> p(N, -1); queue<int> q; p[S] = S; q.push(S); while (!q.empty()) { int x = q.front(); q.pop(); for (auto [y, z] : adj[x]) { if (p[y] == -1) { p[y] = z; q.push(y); } } } priority_queue<int, vector<int>, greater<int>> pq; while (T != S) { for (int v : c[p[T]]) { pq.push(v); } auto [x, y] = edges[p[T]]; T ^= x ^ y; } while (!pq.empty() && pq.top() <= Y) { Y -= pq.top(); pq.pop(); } X -= pq.size(); X = max(X, -1); cout << X << "\n"; } return 6/22; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...