oj.uz

Submission #732327

# Submission time Handle Problem Language Result Execution time Memory
732327 2023-04-29T02:03:36 Z yeyso Two Currencies (JOI23_currencies) C++14
10 / 100
 5000 ms 56264 KB 
#include <bits/stdc++.h>
using namespace std;
//#define long long long long;
vector<vector<long long>> adj;
vector<vector<long long>> ddj;
vector<vector<long long>> rdj;
vector<vector<long long>> roads;
vector<vector<long long>> che;
long long solve(long long s, long long t, long long x, long long y, long long n){
    // road, node, parent
    queue<vector<long long>> q;
    q.push({-1, s, s});
    vector<long long> v(n, 0);
    vector<long long> parents(n, 0);
    vector<long long> ru(n, 0);
    parents[s] = -1;
    long long node; long long road; long long parent;
    while(!q.empty()){
        node = q.front()[1]; road = q.front()[0]; parent = q.front()[2];
        q.pop();
        if(!v[node]){ 
            parents[node] = parent;
            ru[node] = road;
            v[node] = 1;
            for(long long i = 0; i < adj[node].size(); i ++){
                q.push({rdj[node][i], adj[node][i], node});
            }
        }
    }
    vector<long long> coins;
    node = t;
    while(parents[node] != node){
        if(ru[node] >= 0){
            for(long long i = 0; i < che[ru[node]].size(); i ++){
                coins.push_back(che[ru[node]][i]);
            }
        }
        node = parents[node];
    } 
    sort(coins.begin(), coins.end());
    for(long long i = 0; i < coins.size(); i ++){
        if(y - coins[i] >= 0){
            y -= coins[i];
        } else {
            x -= 1;
        }
    }
    if(x >= 0){
        return x;
    } else {
        return -1;
    }
}
int main(){
    long long n, m, queries; cin >> n >> m >> queries;
    vector<vector<long long>> adj0(n, vector<long long>());
    vector<vector<long long>> ddj0(n, vector<long long>()); 
    vector<vector<long long>> rdj0(n, vector<long long>());
    vector<vector<long long>> roads;
    long long a, b, p, c;
    for(long long i = 0; i < n - 1; i ++){
        cin >> a >> b; a -= 1; b -= 1;
        roads.push_back({a, b});
    }
    vector<vector<long long>> checkpoints(n-1, vector<long long>());
    for(long long i = 0; i < m; i ++){
        cin >> p >> c;
        p -= 1;
        checkpoints[p].push_back(c);
    }
    for(long long i = 0; i < roads.size(); i ++){
        adj0[roads[i][0]].push_back(roads[i][1]); adj0[roads[i][1]].push_back(roads[i][0]);
        ddj0[roads[i][0]].push_back(roads[i][2]); ddj0[roads[i][1]].push_back(roads[i][2]);
        rdj0[roads[i][0]].push_back(i); rdj0[roads[i][1]].push_back(i);
    }
    adj = adj0; ddj = ddj0; rdj = rdj0; che = checkpoints;
    long long s, t, x, y;
    vector<long long> res;
    for(long long i = 0; i < queries; i ++){
        cin >> s >> t >> x >> y;
        s -= 1; t -= 1;
        res.push_back(solve(s, t, x, y, n));
    }

    for(long long i = 0; i < res.size(); i ++){
        cout << res[i] << "\n";
    }
}
/*
g++ -std=gnu++17 -O2 -pipe -o 7 7.cpp

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

*/

Compilation message

currencies.cpp: In function 'long long int solve(long long int, long long int, long long int, long long int, long long int)':
currencies.cpp:25:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
currencies.cpp:34:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for(long long i = 0; i < che[ru[node]].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:41:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(long long i = 0; i < coins.size(); i ++){
      |                          ~~^~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:71:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(long long i = 0; i < roads.size(); i ++){
      |                          ~~^~~~~~~~~~~~~~
currencies.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(long long i = 0; i < res.size(); i ++){
      |                          ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 243 ms 1356 KB Output is correct
6 Correct 375 ms 1436 KB Output is correct
7 Correct 227 ms 1176 KB Output is correct
8 Correct 413 ms 1468 KB Output is correct
9 Correct 410 ms 1588 KB Output is correct
10 Correct 418 ms 1464 KB Output is correct
11 Correct 451 ms 1460 KB Output is correct
12 Correct 388 ms 1468 KB Output is correct
13 Correct 420 ms 1408 KB Output is correct
14 Correct 382 ms 1412 KB Output is correct
15 Correct 369 ms 1388 KB Output is correct
16 Correct 317 ms 1396 KB Output is correct
17 Correct 350 ms 1376 KB Output is correct
18 Correct 327 ms 1392 KB Output is correct
19 Correct 353 ms 1588 KB Output is correct
20 Correct 350 ms 1708 KB Output is correct
21 Correct 379 ms 1576 KB Output is correct
22 Correct 374 ms 1612 KB Output is correct
23 Correct 460 ms 1484 KB Output is correct
24 Correct 488 ms 1444 KB Output is correct
25 Correct 468 ms 1464 KB Output is correct
26 Correct 428 ms 1588 KB Output is correct
27 Correct 392 ms 1500 KB Output is correct
28 Correct 423 ms 1452 KB Output is correct
29 Correct 398 ms 1524 KB Output is correct
30 Correct 422 ms 1472 KB Output is correct
31 Correct 505 ms 1448 KB Output is correct
32 Correct 412 ms 1592 KB Output is correct
33 Correct 322 ms 1484 KB Output is correct
34 Correct 346 ms 1416 KB Output is correct
35 Correct 322 ms 1524 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 449 ms 1364 KB Output is correct
3 Correct 455 ms 1588 KB Output is correct
4 Correct 411 ms 1708 KB Output is correct
5 Execution timed out 5028 ms 56264 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 337 ms 1444 KB Output is correct
3 Correct 332 ms 1416 KB Output is correct
4 Correct 328 ms 1528 KB Output is correct
5 Execution timed out 5077 ms 50340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 243 ms 1356 KB Output is correct
6 Correct 375 ms 1436 KB Output is correct
7 Correct 227 ms 1176 KB Output is correct
8 Correct 413 ms 1468 KB Output is correct
9 Correct 410 ms 1588 KB Output is correct
10 Correct 418 ms 1464 KB Output is correct
11 Correct 451 ms 1460 KB Output is correct
12 Correct 388 ms 1468 KB Output is correct
13 Correct 420 ms 1408 KB Output is correct
14 Correct 382 ms 1412 KB Output is correct
15 Correct 369 ms 1388 KB Output is correct
16 Correct 317 ms 1396 KB Output is correct
17 Correct 350 ms 1376 KB Output is correct
18 Correct 327 ms 1392 KB Output is correct
19 Correct 353 ms 1588 KB Output is correct
20 Correct 350 ms 1708 KB Output is correct
21 Correct 379 ms 1576 KB Output is correct
22 Correct 374 ms 1612 KB Output is correct
23 Correct 460 ms 1484 KB Output is correct
24 Correct 488 ms 1444 KB Output is correct
25 Correct 468 ms 1464 KB Output is correct
26 Correct 428 ms 1588 KB Output is correct
27 Correct 392 ms 1500 KB Output is correct
28 Correct 423 ms 1452 KB Output is correct
29 Correct 398 ms 1524 KB Output is correct
30 Correct 422 ms 1472 KB Output is correct
31 Correct 505 ms 1448 KB Output is correct
32 Correct 412 ms 1592 KB Output is correct
33 Correct 322 ms 1484 KB Output is correct
34 Correct 346 ms 1416 KB Output is correct
35 Correct 322 ms 1524 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 449 ms 1364 KB Output is correct
38 Correct 455 ms 1588 KB Output is correct
39 Correct 411 ms 1708 KB Output is correct
40 Execution timed out 5028 ms 56264 KB Time limit exceeded
41 Halted 0 ms 0 KB -