# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
781686 | 2023-07-13T09:58:26 Z | YassineBenYounes | Two Currencies (JOI23_currencies) | C++17 | 44 ms | 752 KB |
#include<bits/stdc++.h> typedef long long ll; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update> using namespace __gnu_pbds; #define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ////////////////////Only Clear Code////////////////////////// void usaco_problem(){ freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout); } void init(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE } const int mx = 2e3+5; const int LOG = 25; const ll inf = 1e18; const ll mod = 1e8; vector<pair<int, int>> graph[mx]; vector<int> obstacles[mx]; vector<vector<int>> queries; vector<int> v; vector<pair<int, int>> edges; int nxt = 0; bool dfs(int node, int p){ if(node == nxt){ return 1; } for(pair<int, int> adj : graph[node]){ if(adj.first == p)continue; for(int x : obstacles[adj.second]){ v.push_back(x); } if(dfs(adj.first, node))return 1; for(int x : obstacles[adj.second]){ v.pop_back(); } } return 0; } void run_case(){ int n, m, q;cin >> n >> m >> q; for(int i = 0; i < n-1;i++){ int a, b;cin >> a >> b; graph[a].push_back({b, i+1}); graph[b].push_back({a, i+1}); if(a > b)swap(a, b); edges.push_back({a, b}); } for(int i = 0; i < m;i++){ int a, b;cin >> a >> b; obstacles[a].push_back(b); } for(int i = 0; i < q;i++){ int a, b, gold, silver;cin >> a >> b >> gold >> silver; queries.push_back({a, b, gold, silver}); v.clear(); nxt = b; dfs(a, a); /*for(int x : v){ cout << x << " "; } cout << endl;*/ sort(v.begin(), v.end(), greater<int>()); while(!v.empty() && silver > v.back()){ silver -= v.back(); v.pop_back(); } gold -= v.size(); gold = max(gold, -1); cout << gold << endl; } } int main(){ speed; int t = 1; //cin >> t; while(t--){ run_case(); } } /* NEVER GIVE UP! DOING SMTHNG IS BETTER THAN DOING NTHNG!!! Your Guide when stuck: - Continue keyword only after reading the whole input - Don't use memset with testcases - Check for corner cases(n=1, n=0) - Check where you declare n(Be careful of declaring it globally and in main) */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 416 KB | Output is correct |
2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Incorrect | 44 ms | 752 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 416 KB | Output is correct |
2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |