Submission #955838

#	Time	Username	Problem	Language	Result	Execution time	Memory
955838		Ludissey	Two Currencies (JOI23_currencies)	C++14	28 / 100	320 ms	56704 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
const int LOG=20;

using namespace std;
vector<int> dist;
vector<int> depth;
vector<int> sum;
vector<int> sum2;

vector<vector<int>> parent;
vector<vector<pair<int,int>>> child;
vector<vector<pair<int,int>>> neigh;
vector<pair<int,pair<int,int>>> edges;
vector<int> v;


void make_tree(int x, int p){
    parent[x][0]=p;
    depth[x]=depth[p]+1;
    for (auto u : neigh[x])
    {
        if(u.first==p) continue;
        sum[u.first]=sum[x]+u.second;
        make_tree(u.first,x);
        child[x].push_back({u.first,u.second});
    }
}


int lca(int a, int b){
    if(depth[a]>depth[b]) swap(a,b);
    int d=depth[b]-depth[a];
    for (int j = LOG-1; j >= 0; j--) {
        if(d&(1<<j)) b=parent[b][j];
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0; j--) {
        if(parent[a][j]!=parent[b][j]) {
            a=parent[a][j];
            b=parent[b][j];
        }
    }
    return parent[a][0];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,m,q; cin >> n >> m >> q;
    edges.resize(n-1);
    depth.resize(n);
    sum.resize(n,0);
    dist.resize(n);
    child.resize(n);
    neigh.resize(n);
    parent.resize(n, vector<int>(LOG, 0));
    int totalSUM=0;
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        edges[i]={0,{a-1,b-1}};
    }
    for (int i = 0; i < m; i++){
        int p,c; cin >> p >> c;
        edges[p-1].first+=c;
        totalSUM+=c;
        v.push_back(c);
    }
    for (int i = 0; i < n-1; i++){
        int a=edges[i].second.first,b=edges[i].second.second,c=edges[i].first;
        neigh[a].push_back({b,c});
        neigh[b].push_back({a,c});
    }
    make_tree(0,0);
    depth[0]=0;
    for (int j = 1; j < LOG; j++) for (int i = 0; i < n; i++) parent[i][j]=parent[parent[i][j-1]][j-1];
    sort(v.begin(),v.end());
    for (int i = 1; i < sz(v); i++) v[i]+=v[i-1];
    while(q--)
    {
        int s,t,x,y; cin >> s >> t >> x >> y;
        int lc=lca(s-1,t-1);
        int sm=-2*sum[lc]+sum[t-1]+sum[s-1];
        sm=totalSUM-sm;
        int lb=upper_bound(v.begin(),v.end(), sm+y)-v.begin();
        int u=(sz(v))-lb;
        cout << max(-1LL, x-u) << "\n";
    }
    return 0;
}

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