Submission #838073

#	Time	Username	Problem	Language	Result	Execution time	Memory
838073		fatemetmhr	Two Currencies (JOI23_currencies)	C++17	100 / 100	926 ms	47480 KiB

currencies

// na hanooz omidi vjood dare... hanooz ye karayi hast ke bknm :)

#include <bits/stdc++.h>

using namespace std;


#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   (x).begin(), (x).end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const int maxn5 = 1e5 + 10;
const int lg    = 20;

int ti = 3, st[maxn5], ft[maxn5], h[maxn5];
int hcnt[maxn5], cnt[maxn5], s[maxn5], t[maxn5];
int par[lg][maxn5], a[maxn5], b[maxn5], c[maxn5];
int lo[maxn5], hi[maxn5];
ll x[maxn5], y[maxn5], mx[maxn5];
pair <int, int> p[maxn5];
vector <int> req[maxn5];
vector <pair<int, int>> adj[maxn5];


pair <ll, int> operator +(pair <ll, int> a, pair <ll, int> b){
	return mp(a.fi + b.fi, a.se + b.se);
}

pair <ll, int> operator -(pair <ll, int> a, pair <ll, int> b){
	return mp(a.fi - b.fi, a.se - b.se);
}

pair <ll, int> operator *(int a, pair <ll, int> b){
	return mp(a * b.fi, a * b.se);
}

namespace fen{

	pair <ll, int> fen[maxn5];

	void clear(){
		memset(fen, 0, sizeof fen);
	}

	pair <ll, int> get(int id){
		pair<ll, int> ret = {0, 0};
		for(; id; id -= id & -id)
			ret = ret + fen[id];
		return ret;
	}

	void add(int id, pair <ll, int> val){
		for(; id < maxn5; id += id & -id)
			fen[id] = fen[id] + val;
	}

	void add(int l, int r, ll val){
		//debug("Adding ");
		//debug(l);
		//debug(r);
		//debug(val);
		add(l, mp(val, 1));
		add(r + 1, mp(-val, -1));
	}
}

int lca(int a, int b){
	if(h[a] < h[b])
		swap(a, b);
	int d = h[a] - h[b];
	for(int i = 0; i < lg; i++) if((d >> i)&1)
		a = par[i][a];
	if(a == b)
		return a;
	for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){
		a = par[i][a];
		b = par[i][b];
	}
	return par[0][a];
}

void dfs_lca(int v){
	for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
		par[i][v] = par[i - 1][par[i - 1][v]];
	st[v] = ++ti;
	for(auto [u, id] : adj[v]) if(u != par[0][v]){
		h[u] = h[v] + 1;
		hcnt[u] = hcnt[v] + cnt[id];
		par[0][u] = v;
		dfs_lca(u);
	}
	ft[v] = ti;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < n - 1; i++){
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		adj[a[i]].pb({b[i], i});
		adj[b[i]].pb({a[i], i});
	}



	for(int i = 0; i < m; i++){
		cin >> p[i].se >> p[i].fi;
		p[i].se--;
		cnt[p[i].se]++;
	}
	sort(p, p + m);

	memset(par, -1, sizeof par);
	dfs_lca(0);


	for(int i = 0; i < n - 1; i++)
		if(h[a[i]] > h[b[i]])
			swap(a[i], b[i]);

	memset(lo, -1, sizeof lo);
	fill(hi, hi + q + 4, m);
	for(int i = 0; i < q; i++){
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		s[i]--; t[i]--;
		c[i] = lca(s[i], t[i]);
	}

	bool con = true;
	while(con){
		con = false;
		fen::clear();
		for(int i = 0; i < q; i++) if(hi[i] - lo[i] > 1){
			con = true;
			req[(hi[i] + lo[i]) >> 1].pb(i);
		}
		for(int i = 0; i < m; i++){
			fen::add(st[b[p[i].se]], ft[b[p[i].se]], p[i].fi);
			//debug(b[p[i].se]);
			for(auto id : req[i]){
				//debug(st[s[id]]);
				//debug(st[t[id]]);
				//debug(fen::get(st[s[id]]).se);
				//debug(fen::get(st[t[id]]).se);
				pair <ll, int> val = fen::get(st[s[id]]) + fen::get(st[t[id]]) - (2 * fen::get(st[c[id]]));
				if(val.fi <= y[id]){
					//debug(i);
					//debug(id);
					//debug(val.fi);
					//debug(val.se);
					lo[id] = i;
					mx[id] = val.se;
				}
				else
					hi[id] = i;
			}
			req[i].clear();
		}
	}

	for(int i = 0; i < q; i++){
		//debug(mx[i]);
		cout << max(-1ll, x[i] - (hcnt[s[i]] + hcnt[t[i]] - 2 * hcnt[c[i]] - mx[i])) << '\n';
	}

}

Compilation message (stderr)

currencies.cpp: In function 'void fen::clear()':
currencies.cpp:47:28: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   47 |   memset(fen, 0, sizeof fen);
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from currencies.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~

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