oj.uz

Submission #781708

# Submission time Handle Problem Language Result Execution time Memory
781708 2023-07-13T10:17:15 Z YassineBenYounes Two Currencies (JOI23_currencies) C++17
0 / 100
 3 ms 4948 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 = 2e5+5;
const int LOG = 25;
const ll inf = 1e18;
const ll mod = 1e8;

vector<pair<int, int>> graph[mx];

ll obstacles[mx];

vector<vector<int>> queries;

vector<pair<int, int>> edges;

int anc[mx][LOG], dis[mx];

void dfs(int node, int p){
    anc[node][0] = p;
    for(int j = 1; j < 20;j++)anc[node][j] = anc[anc[node][j-1]][j-1];
    for(pair<int, int> adj : graph[node]){
        if(adj.first == p)continue;
        dis[adj.first] = dis[node]+1;
        dfs(adj.first, node);
    }
}

void dfs1(int node, int p){
    for(pair<int, int> adj : graph[node]){
        if(adj.first == p)continue;
        obstacles[adj.first] += obstacles[node];
        dfs1(adj.first, node);
    }
}

int lca(int a, int b){
    if(dis[b] > dis[a])swap(a, b);
    int k = dis[a] - dis[b];
    for(int j = 20; j >= 0;j--){
        if(k & (1 << j)){
            a = anc[a][j];
        }
    }
    if(a == b)return a;
    for(int j = 20; j >= 0;j--){
        if(dis[a] >= (1 << j) && anc[a][j] != anc[b][j]){
            a = anc[a][j];
            b = anc[b][j];
        }
    }
    return anc[a][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});
    }
    dfs(1, 1);
    ll one = 0;
    for(int i = 0; i < m;i++){
        int a, b;cin >> a >> b;a--;
        one = b;
        int x = edges[a].first, y = edges[a].second;
        if(x == anc[y][0])swap(x, y);
        obstacles[x]++;
    }
    dfs1(1, 1);
    for(int i = 0; i < q;i++){
        ll a, b, gold, silver;cin >> a >> b >> gold >> silver;
        ll k = lca(a, b);
        ll tot = obstacles[a] + obstacles[b] - 2*obstacles[k];
        //cout << a << " " << b << " " << tot << endl;
        ll left = tot - (silver / one);
        gold -= left;
        cout << max(gold, (ll)-1) << 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 '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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -