oj.uz

Submission #732404

# Submission time Handle Problem Language Result Execution time Memory
732404 2023-04-29T03:45:08 Z yeyso Two Currencies (JOI23_currencies) C++14
10 / 100
 553 ms 142472 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;
// BRUTE FORCE
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;
    }
} 
// LCA
vector<long long> visited;
vector<long long> euler;
vector<long long> first;
vector<long long> height;
vector<long long> prefix;
void dfs(long long u, long long h, long long r) {
    visited[u] = 1;
    euler.push_back(u);
    first[u] = euler.size() - 1;
    height[u] = h;
    /*if(r >= 0){
        prefix.push_back(che[r].size());
    }*/
    //cout << u;
    for (long long i = 0; i < adj[u].size(); i ++){
        if (!visited[adj[u][i]]){
            dfs(adj[u][i], h + 1, rdj[u][i]);
            /*if(r >= 0){
                prefix.push_back(che[r].size());
            }*/
            euler.push_back(u);
        }
    }
}
vector<long long> tolls;
void dfs2(long long u, long long p, long long delta) {
    visited[u] = 1;
    tolls[u] = tolls[p] + delta;
    for (long long i = 0; i < adj[u].size(); i ++){
        if (!visited[adj[u][i]]){
            dfs2(adj[u][i], u, che[rdj[u][i]].size());
        }
    }
}
vector<pair<long long, long long>> tree(4e5+5, pair<long long, long long>());
void upd(long long i, long long val, long long node, long long lbound, long long rbound, long long j = 1){
    if(i < lbound || rbound < i){
        return;
    }
    if(lbound == rbound){
        tree[j] = {val, node};
        return;
    }
    long long mid = (lbound + rbound) / 2;
    upd(i, val, node, lbound, mid, j * 2);
    upd(i, val, node, mid+1, rbound, j * 2 + 1);
    tree[j] = min(tree[j * 2], tree[j * 2 + 1]);
}
pair<long long, long long> rangeq(long long ql, long long qr, long long lbound, long long rbound, long long j = 1){
    if(qr < lbound || rbound < ql){
        return {LONG_LONG_MAX / 2, 0};
    }
    if(ql <= lbound and rbound <= qr){
        return tree[j];
    }
    long long mid = (lbound + rbound) / 2;
    pair<long long, long long> left_value = rangeq(ql, qr, lbound, mid, j * 2);
    pair<long long, long long> right_value = rangeq(ql, qr, mid+1, rbound, j * 2 + 1);
    if(left_value.first < right_value.first){
        return left_value;
    } else {
        return right_value;
    }
}
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;
    map<pair<long long, long long>, long long> ab_to_road;
    long long subtask2 = 1;
    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});
        ab_to_road[{min(a, b), max(a, b)}] = i;
    }
    vector<vector<long long>> check(n-1, vector<long long>());
    long long pc = 0;
    for(long long i = 0; i < m; i ++){
        cin >> p >> c;
        if(i == 0){
            pc = c;
        } else {
            if(c != pc){
                subtask2 = 0;
            }
            pc = c;
        }
        p -= 1;
        check[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 = check;
    vector<long long> v0(n, 0);
    visited = v0; first = v0; height = v0;
    long long s, t, x, y;
    vector<long long> res;
    dfs(0, 0, -1);
    visited = v0;
    tolls = v0;
    long long tc = 0;
    long long silver = 0;
    long long gold = 0;
    dfs2(0, 0, 0);
    for(long long i = 0; i < euler.size(); i ++){
        upd(i, height[euler[i]], euler[i], 0, euler.size());
    }
    
    for(long long i = 0; i < queries; i ++){
        cin >> s >> t >> x >> y;
        s -= 1; t -= 1;

        if(!subtask2){
            res.push_back(solve(s, t, x, y, n));
        } else {
            tc = (tolls[s] + tolls[t] - 2 * tolls[rangeq(min(first[s], first[t]), max(first[s], first[t]), 0, euler.size()).second]);
            //silver = y / c;
            tc -= y / c;
            x -= max(0ll, tc);

            res.push_back(max(-1ll, x));
        }
    }

    for(long long i = 0; i < res.size(); i ++){
        cout << res[i] << "\n";
    }
    vector<long long> roadsfix(n-1, 0);
    vector<long long> prefix2;
    vector<long long> dp(n-1, 0);
    /*if(subtask2){
        //cout << 'FORTNITE';
        //cout << "|-";

        for(long long i = 0; i < euler.size(); i ++){
            cout << euler[i] + 1 << " ";

            /*if(i >= 1){
                prefix.push_back(ab_to_road[{min(euler[i], euler[i-1]), max(euler[i], euler[i-1])}]);
            }
        } cout << "\n";
        prefix2.push_back(0);
        for(long long i = 0; i < prefix.size(); i ++){
            if(!dp[prefix[i]]){
                //cout << prefix[i] + 1 << " ";
                prefix2.push_back(prefix2[i] + 1);
                dp[prefix[i]] = 1;
            } else {
                prefix2.push_back(prefix2[i] - 1);
                //cout << 0 << " ";
            }
        }
        for(long long i = 0; i < tolls.size(); i ++){
            cout << i + 1 << " ";
        } cout << "\n";
        for(long long i = 0; i < tolls.size(); i ++){
            cout << tolls[i] << " ";
        }
    }*/
}
/*
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

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3


*/

Compilation message

currencies.cpp:199:13: warning: "/*" within comment [-Wcomment]
  199 |             /*if(i >= 1){
      |              
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:26: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]
   26 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
currencies.cpp:35: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]
   35 |             for(long long i = 0; i < che[ru[node]].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:42: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]
   42 |     for(long long i = 0; i < coins.size(); i ++){
      |                          ~~^~~~~~~~~~~~~~
currencies.cpp: In function 'void dfs(long long int, long long int, long long int)':
currencies.cpp:70:29: 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]
   70 |     for (long long i = 0; i < adj[u].size(); i ++){
      |                           ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void dfs2(long long int, long long int, long long int)':
currencies.cpp:84:29: 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]
   84 |     for (long long i = 0; i < adj[u].size(); i ++){
      |                           ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:149: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]
  149 |     for(long long i = 0; i < roads.size(); i ++){
      |                          ~~^~~~~~~~~~~~~~
currencies.cpp:166: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]
  166 |     for(long long i = 0; i < euler.size(); i ++){
      |                          ~~^~~~~~~~~~~~~~
currencies.cpp:186: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]
  186 |     for(long long i = 0; i < res.size(); i ++){
      |                          ~~^~~~~~~~~~~~
currencies.cpp:163:15: warning: unused variable 'silver' [-Wunused-variable]
  163 |     long long silver = 0;
      |               ^~~~~~
currencies.cpp:164:15: warning: unused variable 'gold' [-Wunused-variable]
  164 |     long long gold = 0;
      |               ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 5 ms 6532 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 240 ms 7852 KB Output is correct
6 Correct 440 ms 7956 KB Output is correct
7 Correct 253 ms 7500 KB Output is correct
8 Correct 444 ms 7976 KB Output is correct
9 Correct 479 ms 7984 KB Output is correct
10 Correct 493 ms 7956 KB Output is correct
11 Correct 421 ms 7972 KB Output is correct
12 Correct 481 ms 7972 KB Output is correct
13 Correct 408 ms 8024 KB Output is correct
14 Correct 433 ms 8116 KB Output is correct
15 Correct 371 ms 7948 KB Output is correct
16 Correct 359 ms 7932 KB Output is correct
17 Correct 397 ms 7916 KB Output is correct
18 Correct 341 ms 7948 KB Output is correct
19 Correct 378 ms 8088 KB Output is correct
20 Correct 380 ms 8092 KB Output is correct
21 Correct 553 ms 8092 KB Output is correct
22 Correct 429 ms 8092 KB Output is correct
23 Correct 522 ms 7996 KB Output is correct
24 Correct 523 ms 7980 KB Output is correct
25 Correct 501 ms 8080 KB Output is correct
26 Correct 449 ms 8104 KB Output is correct
27 Correct 389 ms 8012 KB Output is correct
28 Correct 403 ms 8100 KB Output is correct
29 Correct 434 ms 7892 KB Output is correct
30 Correct 11 ms 7900 KB Output is correct
31 Correct 11 ms 7860 KB Output is correct
32 Correct 11 ms 7864 KB Output is correct
33 Correct 315 ms 8048 KB Output is correct
34 Correct 400 ms 8048 KB Output is correct
35 Correct 317 ms 8032 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 10 ms 7840 KB Output is correct
3 Correct 10 ms 7892 KB Output is correct
4 Correct 11 ms 7860 KB Output is correct
5 Runtime error 388 ms 142296 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 3 ms 6484 KB Output is correct
2 Correct 324 ms 7964 KB Output is correct
3 Correct 333 ms 8168 KB Output is correct
4 Correct 319 ms 8040 KB Output is correct
5 Runtime error 254 ms 142472 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 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 5 ms 6532 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 240 ms 7852 KB Output is correct
6 Correct 440 ms 7956 KB Output is correct
7 Correct 253 ms 7500 KB Output is correct
8 Correct 444 ms 7976 KB Output is correct
9 Correct 479 ms 7984 KB Output is correct
10 Correct 493 ms 7956 KB Output is correct
11 Correct 421 ms 7972 KB Output is correct
12 Correct 481 ms 7972 KB Output is correct
13 Correct 408 ms 8024 KB Output is correct
14 Correct 433 ms 8116 KB Output is correct
15 Correct 371 ms 7948 KB Output is correct
16 Correct 359 ms 7932 KB Output is correct
17 Correct 397 ms 7916 KB Output is correct
18 Correct 341 ms 7948 KB Output is correct
19 Correct 378 ms 8088 KB Output is correct
20 Correct 380 ms 8092 KB Output is correct
21 Correct 553 ms 8092 KB Output is correct
22 Correct 429 ms 8092 KB Output is correct
23 Correct 522 ms 7996 KB Output is correct
24 Correct 523 ms 7980 KB Output is correct
25 Correct 501 ms 8080 KB Output is correct
26 Correct 449 ms 8104 KB Output is correct
27 Correct 389 ms 8012 KB Output is correct
28 Correct 403 ms 8100 KB Output is correct
29 Correct 434 ms 7892 KB Output is correct
30 Correct 11 ms 7900 KB Output is correct
31 Correct 11 ms 7860 KB Output is correct
32 Correct 11 ms 7864 KB Output is correct
33 Correct 315 ms 8048 KB Output is correct
34 Correct 400 ms 8048 KB Output is correct
35 Correct 317 ms 8032 KB Output is correct
36 Correct 4 ms 6484 KB Output is correct
37 Correct 10 ms 7840 KB Output is correct
38 Correct 10 ms 7892 KB Output is correct
39 Correct 11 ms 7860 KB Output is correct
40 Runtime error 388 ms 142296 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -