Submission #1086626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086626		Tozzyyyy	Two Currencies (JOI23_currencies)	C++17	0 / 100	23 ms	17240 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) 
#define lowbit(x) (x&(-x))
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 A[MAXN], B[MAXN], n;
void upd(int x, int v) {
  for(int i = x ; i <= n ; i += lowbit(i)) B[i] += v;
}
int sum(int x) {
  int ans = 0;
  for(int i = x ; i > 0 ; i -= lowbit(i)) ans += B[i];
  return ans;
}
void update(int l, int r, int v) {
  upd(r + 1, -v); upd(l, v);
}
void init(int _n) {
	n = _n;
  fill(B, B + n + 1, 0); A[0] = 0;
  for(int i = 1 ; i <= n ; ++i) upd(i, A[i] - A[i - 1]);
}
};

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.sum(x) * t;
		Q[id].c += Bit2.sum(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];
			jj++;
			if(a[l] == w) cnt[l]++;
			if(l >= 2) Bit2.update(1 , l - 1 , 1);
			if(l <= a.size()) Bit1.update(l, a.size() , w);
		}
		dfs(v , a);
		jj = 0;
		for(auto w : W){
			l = id[jj];
			jj++;
			if(a[l] == w) cnt[l]--;
			if(l >= 2) Bit2.update(1 , l - 1 , -1);
			if(l <= a.size()) Bit1.update(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 dfs(int, const std::vector<int>&)':
currencies.cpp:103:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    if(l <= a.size()) Bit1.update(l, a.size() , w);
      |       ~~^~~~~~~~~~~
currencies.cpp:112:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    if(l <= a.size()) Bit1.update(l, a.size() , -w);
      |       ~~^~~~~~~~~~~

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