Submission #782304

#	Time	Username	Problem	Language	Result	Execution time	Memory
782304		AmirElarbi	Two Currencies (JOI23_currencies)	C++14	28 / 100	270 ms	32256 KiB

currencies

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace __gnu_pbds;
using namespace std;
const int nax = 1e5+5;
const int kax = 25+5;
const int MOD = 1e9+7;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int cnt = 0, cur = 0, tin[nax], tout[nax], up[nax][kax];
vii adj[nax];
ll dep[nax], w[nax];
void dfs(int u, int p){
    tin[u] = cur++;
    up[u][0] = p;
    for(int i = 1; i < kax; i++)
        up[u][i] = up[up[u][i-1]][i-1];
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        dep[x.fi] = dep[u]+w[x.se];
        dfs(x.fi,u);
    }
    tout[u] = cur++;
}
bool is_anc(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int i = kax-1; i >= 0; i--)
        if(!is_anc(up[u][i], v)) u = up[u][i];
    return up[u][0];
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    for (int i = 0; i < n-1; ++i)
    {
        int a,b;
        cin >> a >> b;
        a--,b--;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    for (int i = 0; i < m; ++i)
    {
        int p;
        ll c;
        cin >> p >> c;
        p--;
        cnt = c;
        w[p] += c;
    }
    dfs(0,0);
    //cout << up[6][0] << endl;
    while(q--){
        int s,t,x;
        ll y;
        cin >> s >> t >> x >> y;
        s--,t--;
        int l = lca(s,t);
        ll sm = dep[s]+dep[t]-2*dep[l];
        ll gld = sm/cnt - y/cnt;
        //cout << l << endl;
        if(gld <= 0) cout << x << endl;
        else if(gld <= x) cout << x-gld << endl;
        else cout << -1 << endl; 
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 28 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32