oj.uz

Submission #732408

# Submission time Handle Problem Language Result Execution time Memory
732408 2023-04-29T03:47:38 Z yeyso Two Currencies (JOI23_currencies) C++14
10 / 100
 457 ms 140260 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()-1);
    }
    
    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()-1).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 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 215 ms 7784 KB Output is correct
6 Correct 382 ms 7832 KB Output is correct
7 Correct 226 ms 7432 KB Output is correct
8 Correct 448 ms 8024 KB Output is correct
9 Correct 415 ms 7892 KB Output is correct
10 Correct 415 ms 7920 KB Output is correct
11 Correct 399 ms 8020 KB Output is correct
12 Correct 440 ms 7892 KB Output is correct
13 Correct 376 ms 8064 KB Output is correct
14 Correct 381 ms 7924 KB Output is correct
15 Correct 342 ms 7856 KB Output is correct
16 Correct 327 ms 7852 KB Output is correct
17 Correct 377 ms 7952 KB Output is correct
18 Correct 321 ms 7972 KB Output is correct
19 Correct 357 ms 8128 KB Output is correct
20 Correct 341 ms 8016 KB Output is correct
21 Correct 367 ms 8012 KB Output is correct
22 Correct 372 ms 8020 KB Output is correct
23 Correct 447 ms 7912 KB Output is correct
24 Correct 457 ms 7884 KB Output is correct
25 Correct 449 ms 7896 KB Output is correct
26 Correct 393 ms 7884 KB Output is correct
27 Correct 414 ms 7872 KB Output is correct
28 Correct 399 ms 7876 KB Output is correct
29 Correct 386 ms 7884 KB Output is correct
30 Correct 10 ms 7764 KB Output is correct
31 Correct 13 ms 7764 KB Output is correct
32 Correct 10 ms 7764 KB Output is correct
33 Correct 322 ms 8072 KB Output is correct
34 Correct 321 ms 7944 KB Output is correct
35 Correct 318 ms 7952 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 10 ms 7844 KB Output is correct
3 Correct 12 ms 7772 KB Output is correct
4 Correct 10 ms 7764 KB Output is correct
5 Runtime error 409 ms 139688 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 364 ms 8064 KB Output is correct
3 Correct 342 ms 7960 KB Output is correct
4 Correct 319 ms 7980 KB Output is correct
5 Runtime error 293 ms 140260 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 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 215 ms 7784 KB Output is correct
6 Correct 382 ms 7832 KB Output is correct
7 Correct 226 ms 7432 KB Output is correct
8 Correct 448 ms 8024 KB Output is correct
9 Correct 415 ms 7892 KB Output is correct
10 Correct 415 ms 7920 KB Output is correct
11 Correct 399 ms 8020 KB Output is correct
12 Correct 440 ms 7892 KB Output is correct
13 Correct 376 ms 8064 KB Output is correct
14 Correct 381 ms 7924 KB Output is correct
15 Correct 342 ms 7856 KB Output is correct
16 Correct 327 ms 7852 KB Output is correct
17 Correct 377 ms 7952 KB Output is correct
18 Correct 321 ms 7972 KB Output is correct
19 Correct 357 ms 8128 KB Output is correct
20 Correct 341 ms 8016 KB Output is correct
21 Correct 367 ms 8012 KB Output is correct
22 Correct 372 ms 8020 KB Output is correct
23 Correct 447 ms 7912 KB Output is correct
24 Correct 457 ms 7884 KB Output is correct
25 Correct 449 ms 7896 KB Output is correct
26 Correct 393 ms 7884 KB Output is correct
27 Correct 414 ms 7872 KB Output is correct
28 Correct 399 ms 7876 KB Output is correct
29 Correct 386 ms 7884 KB Output is correct
30 Correct 10 ms 7764 KB Output is correct
31 Correct 13 ms 7764 KB Output is correct
32 Correct 10 ms 7764 KB Output is correct
33 Correct 322 ms 8072 KB Output is correct
34 Correct 321 ms 7944 KB Output is correct
35 Correct 318 ms 7952 KB Output is correct
36 Correct 3 ms 6484 KB Output is correct
37 Correct 10 ms 7844 KB Output is correct
38 Correct 12 ms 7772 KB Output is correct
39 Correct 10 ms 7764 KB Output is correct
40 Runtime error 409 ms 139688 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -