Submission #1086623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086623		Tozzyyyy	Two Currencies (JOI23_currencies)	C++14	0 / 100	5051 ms	15964 KiB

currencies

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma,bmi")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long , long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
using namespace std;

const long long inf = 1e18+1; 
const int mod = 998244353; 
const int MAXN = 1e5+100;

#define ll long long

struct Fen{
	int n;
    vector<ll>bit1, bit2;
    void init(ll _n){
		 n = _n + 10;
		bit1.clear(); bit2.clear();
		bit1.resize(_n + 10, 0), bit2.resize(_n + 10 , 0);
	};
    void updatePoint(vector<ll>& b, int u, ll v) {
        int idx = u;
        while (idx <= n) {
            b[idx] = (b[idx] + v);
            idx += (idx & (-idx));
        }
    }
    void updateRange(int l, int r, ll v) {
        updatePoint(bit1, l, ((n - l + 1) * v));
        updatePoint(bit1, r + 1, (-(n - r) * v));
        updatePoint(bit2, l, v);
        updatePoint(bit2, r + 1, -v);
    }
    ll getSum(vector<ll>& b, ll u) {
        ll idx = u, ans = 0;
        while (idx > 0) {
            ans = (ans + b[idx]);
            idx -= (idx & (-idx));
        }
        return ans;
    }
    ll prefixSum(ll u) {
        ll x = (getSum(bit1, u) - (getSum(bit2, u) * (n - u)));
        return x;
    }
    ll rangeSum(int l, int r) {
        ll x = (prefixSum(r) - prefixSum(l - 1));
        return x;
    }
};

struct query{
	long long remain , y; 
	int s , t , p , x , l , r , m , ans , c;
	pll res , T;
};
vector<pair<int , vector<int>>> adj[MAXN];
int h[MAXN] , up[MAXN][18];

void pre_dfs(int u){
	for(auto [v , w] : adj[u]){
		if(v == up[u][0]) continue;
		up[v][0] = u;
		for(int i = 1 ; i <= 17 ; i ++){
			up[v][i] = up[up[v][i-1]][i-1];
		}
		h[v] = h[u] + 1;
		pre_dfs(v);
	}
}

int lca(int u , int v){
	if(h[u] != h[v]){
		if(h[u] < h[v]) swap(u , v);
		int k = h[u] - h[v];
		for(int i = 0 ; i <= 17 ; i ++){
			if(bit(i , k)) u = up[u][i];
		}
	}

	if(u == v) return v;

	for(int i = 17 ; i >= 0 ; i --){
		if(up[u][i] != up[v][i]){
			u = up[u][i] ;  v = up[v][i];
		}
	}
	return up[u][0];
}

struct node{
	int x , t , id;
};
vector<node> v[MAXN];
Fen Bit1 , Bit2;
int m;
query Q[MAXN];

int cnt[MAXN];
void dfs(int u , const vector<int> &a ){
	for(auto [x , t , id] : v[u]){
		Q[id].res.se += cnt[x];
		Q[id].res.fi += Bit1.rangeSum(x , x) * t;
		Q[id].c += Bit2.rangeSum(x , x) * t;
	}
	if(v[u].size()) v[u].clear();
	for(auto [v , W] : adj[u]){
		if(v == up[u][0]) continue;
		vector<int> id(W.size()); int jj = 0;
		int l;
		for(auto w : W){
			id[jj++] = lower_bound(a.begin() , a.end() , w) - a.begin() + 1;
			l = id[jj];
			if(a[l] == w) cnt[l]++;
			if(l >= 2) Bit2.updateRange(1 , l - 1 , 1);
			if(l <= a.size()) Bit1.updateRange(l, a.size() , w);
		}
		dfs(v , a);
		for(auto w : W){
			l = id[jj];
			if(a[l] == w) cnt[l]--;
			if(l >= 2) Bit2.updateRange(1 , l - 1 , -1);
			if(l <= a.size()) Bit1.updateRange(l, a.size() , -w);
		}
	}
}
vector<int> check[MAXN];
int32_t main(){
  	//freopen("LAURA.inp", "r", stdin);
	//freopen("LAURA.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n , q; cin >> n >> m >> q;
	vector<pll> E(n);
	for(int i = 1 ; i < n ; i++){
		cin >> E[i].fi >> E[i].se;
	}

	for(int i = 1 ; i <= m ; i++){
		int p , c; cin >> p >> c;
		check[p].push_back(c);
	}
	
	for(int i = 1 ; i < n ; i++){
		adj[E[i].fi].push_back({E[i].se , check[i]});
		adj[E[i].se].push_back({E[i].fi , check[i]});
	}
	Bit1.init(q); Bit2.init(q);
	pre_dfs(1);
	for(int i = 1 ; i <= q ; i++){
		cin >> Q[i].s >> Q[i].t >> Q[i].x >> Q[i].y;
		Q[i].l = 0, Q[i].r = 1e9;
		Q[i].ans = -1;
		Q[i].p = lca(Q[i].s , Q[i].t);
	}

	while(1){
		bool flag = 0;
		vector<int> event , a;
		for(int i = 1 ; i <= q ; i++){
			if(Q[i].l <= Q[i].r){
				Q[i].m = (Q[i].l + Q[i].r) >> 1;
				event.push_back(Q[i].m);
				a.push_back(i);
				flag = 1; 
				Q[i].res = {0 , 0}; Q[i].c = 0;
			}
		}

		if(flag == 0) break;

		sort(all(event));
		for(auto x : a){
			int i = lower_bound(all(event) , Q[x].m) - event.begin();
			v[Q[x].s].push_back({i + 1 , 1 , x});
			v[Q[x].t].push_back({i + 1, 1 , x});
			v[Q[x].p].push_back({i + 1, -2 , x});
		}
		dfs(1 , event);
		for(auto x : a){
			if(Q[x].res.fi <= Q[x].y){
				Q[x].remain = Q[x].y - Q[x].res.fi;
				Q[x].ans = Q[x].c ; Q[x].l = Q[x].m + 1;
			}else{
				Q[x].T = {Q[x].m , Q[x].res.se};
				Q[x].r = Q[x].m - 1;
			}
		}
	}

	for(int i = 1 ; i <= q ; i++){
		if(Q[i].T.fi != 0){
			Q[i].ans -= min(Q[i].T.se , Q[i].remain / Q[i].T.fi);
		}
		cout << (Q[i].x - Q[i].ans >= 0 ? Q[i].x - Q[i].ans : -1) << "\n";;
	}
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void pre_dfs(int)':
currencies.cpp:65:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for(auto [v , w] : adj[u]){
      |           ^
currencies.cpp: In function 'void dfs(int, const std::vector<int>&)':
currencies.cpp:105:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |  for(auto [x , t , id] : v[u]){
      |           ^
currencies.cpp:111:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |  for(auto [v , W] : adj[u]){
      |           ^
currencies.cpp:120:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    if(l <= a.size()) Bit1.updateRange(l, a.size() , w);
      |       ~~^~~~~~~~~~~
currencies.cpp:127:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    if(l <= a.size()) Bit1.updateRange(l, a.size() , -w);
      |       ~~^~~~~~~~~~~

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