oj.uz

Submission #781689

# Submission time Handle Problem Language Result Execution time Memory
781689 2023-07-13T10:03:00 Z YassineBenYounes Two Currencies (JOI23_currencies) C++17
10 / 100
 114 ms 852 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++){
        ll a, b, gold, silver;cin >> a >> b >> gold >> silver;
        //queries.push_back({a, b, gold, silver});
        v.clear();
        nxt = b;
        dfs(a, a);
        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, (ll)-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

currencies.cpp: In function 'bool dfs(int, int)':
currencies.cpp:48:17: warning: unused variable 'x' [-Wunused-variable]
   48 |         for(int x : obstacles[adj.second]){
      |                 ^
currencies.cpp: In function 'void usaco_problem()':
currencies.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void init()':
currencies.cpp:19:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:21:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 14 ms 548 KB Output is correct
6 Correct 24 ms 644 KB Output is correct
7 Correct 16 ms 592 KB Output is correct
8 Correct 27 ms 596 KB Output is correct
9 Correct 30 ms 640 KB Output is correct
10 Correct 32 ms 596 KB Output is correct
11 Correct 35 ms 596 KB Output is correct
12 Correct 25 ms 560 KB Output is correct
13 Correct 114 ms 836 KB Output is correct
14 Correct 99 ms 852 KB Output is correct
15 Correct 62 ms 716 KB Output is correct
16 Correct 54 ms 596 KB Output is correct
17 Correct 48 ms 628 KB Output is correct
18 Correct 67 ms 724 KB Output is correct
19 Correct 19 ms 636 KB Output is correct
20 Correct 19 ms 596 KB Output is correct
21 Correct 22 ms 644 KB Output is correct
22 Correct 22 ms 596 KB Output is correct
23 Correct 80 ms 596 KB Output is correct
24 Correct 81 ms 624 KB Output is correct
25 Correct 67 ms 596 KB Output is correct
26 Correct 13 ms 552 KB Output is correct
27 Correct 47 ms 596 KB Output is correct
28 Correct 38 ms 596 KB Output is correct
29 Correct 43 ms 552 KB Output is correct
30 Correct 25 ms 548 KB Output is correct
31 Correct 24 ms 560 KB Output is correct
32 Correct 25 ms 636 KB Output is correct
33 Correct 80 ms 724 KB Output is correct
34 Correct 81 ms 852 KB Output is correct
35 Correct 82 ms 852 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 29 ms 552 KB Output is correct
3 Correct 24 ms 552 KB Output is correct
4 Correct 26 ms 596 KB Output is correct
5 Runtime error 1 ms 596 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 79 ms 740 KB Output is correct
3 Correct 81 ms 852 KB Output is correct
4 Correct 94 ms 848 KB Output is correct
5 Runtime error 1 ms 812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 14 ms 548 KB Output is correct
6 Correct 24 ms 644 KB Output is correct
7 Correct 16 ms 592 KB Output is correct
8 Correct 27 ms 596 KB Output is correct
9 Correct 30 ms 640 KB Output is correct
10 Correct 32 ms 596 KB Output is correct
11 Correct 35 ms 596 KB Output is correct
12 Correct 25 ms 560 KB Output is correct
13 Correct 114 ms 836 KB Output is correct
14 Correct 99 ms 852 KB Output is correct
15 Correct 62 ms 716 KB Output is correct
16 Correct 54 ms 596 KB Output is correct
17 Correct 48 ms 628 KB Output is correct
18 Correct 67 ms 724 KB Output is correct
19 Correct 19 ms 636 KB Output is correct
20 Correct 19 ms 596 KB Output is correct
21 Correct 22 ms 644 KB Output is correct
22 Correct 22 ms 596 KB Output is correct
23 Correct 80 ms 596 KB Output is correct
24 Correct 81 ms 624 KB Output is correct
25 Correct 67 ms 596 KB Output is correct
26 Correct 13 ms 552 KB Output is correct
27 Correct 47 ms 596 KB Output is correct
28 Correct 38 ms 596 KB Output is correct
29 Correct 43 ms 552 KB Output is correct
30 Correct 25 ms 548 KB Output is correct
31 Correct 24 ms 560 KB Output is correct
32 Correct 25 ms 636 KB Output is correct
33 Correct 80 ms 724 KB Output is correct
34 Correct 81 ms 852 KB Output is correct
35 Correct 82 ms 852 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 29 ms 552 KB Output is correct
38 Correct 24 ms 552 KB Output is correct
39 Correct 26 ms 596 KB Output is correct
40 Runtime error 1 ms 596 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -