Submission #1222702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222702		ByeWorld	Two Currencies (JOI23_currencies)	C++20	100 / 100	1398 ms	89004 KiB

currencies

#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 1e5+10;
const int SQRT = 450;
const int INF = 2e9;
const int MOD = 998244353;
const int LOG = 20;
int sum(int a, int b){ a%=MOD; b%=MOD; return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a%=MOD; b%=MOD; a = (a+MOD+b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te,te);
	return (b%2 ? mul(te,a) : te);
}
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, q;
int ans[MAXN], u[MAXN], v[MAXN];
int idx[MAXN], co[MAXN], s[MAXN], t[MAXN], x[MAXN], y[MAXN];

struct fen {
	pii st[MAXN];
	void bd(){
		for(int i=0; i<=MAXN-10; i++) st[i] = {0, 0};
	}
	pii que(int x){
		pii te = {0, 0};
		for(; x; x-=x&-x) te.fi += st[x].fi, te.se += st[x].se;
		return te;
	}
	void upd(int x, pii p){
		for(; x<=MAXN-10; x+=x&-x) st[x].fi += p.fi, st[x].se += p.se;
	}
} A;

vector<array<int,3>> cek[MAXN];
int cnt[MAXN][4], point[MAXN];
int pr[MAXN];

vector<int> adj[MAXN], tree[MAXN];
int sub[MAXN], root[MAXN], dep[MAXN], par[MAXN], tim[MAXN], day;
void trav(int nw, int pa){
	for(auto nx : tree[nw]){
		if(nx==pa) continue;
		adj[nw].pb(nx);
		trav(nx,nw);
	}
}
void dfs(int nw, int pa){
	sub[nw] = 1; dep[nw] = dep[pa]+1; par[nw] = pa;

	for(auto nx : adj[nw]){
		dfs(nx, nw); sub[nw] += sub[nx];
	}
}
void bd(int nw, int roo){
	tim[nw] = ++day;
	root[nw] = roo;
	if(adj[nw].empty()) return;
	bd(adj[nw][0], roo);

	for(int i=1; i<adj[nw].size(); i++)
		bd(adj[nw][i], adj[nw][i]);
}
pii GET(int x, int y){
	if(x < y) assert(false);
	pii t1 = A.que(x), t2 = A.que(y);
	pii ret = pii(t1.fi-t2.fi, t1.se-t2.se);
	return ret;
}
pii hld(int x, int y){
	pii tot = {0, 0};
	while(root[x] != root[y]){
		if(dep[root[x]] > dep[root[y]]) swap(x, y);
		// gerak y ke root
		// mau dpt node y ke root[y]
		pii que = GET(tim[y], tim[root[y]]-1); // bawah ke atas

		// cout << y << ' ' << root[y] << ' ' << que.fi<<' '<<que.se<<" root\n";
		tot.fi += que.fi; tot.se += que.se;
		y = par[root[y]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	if(x != y){
		// dr node y ke bawahnya x
		// cout << tim[y] <<' '<<tim[x] << " tim\n";
		pii que = GET(tim[y], tim[x]); // bawah ke atas
		tot.fi += que.fi; tot.se += que.se;
		// cout << y << ' ' << x << ' ' << que.fi << ' '<< que.se << " terakhir\n";
	}
	return tot;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1; i<=n-1; i++){
		cin>>u[i]>>v[i]; 
		tree[u[i]].pb(v[i]); tree[v[i]].pb(u[i]);
	}
	trav(1, 0);
	dfs(1, 0);
	for(int i=1; i<=n; i++){
		if(adj[i].empty()) continue;
		for(int j=1; j<adj[i].size(); j++)
			if(sub[ adj[i][0] ] < sub[ adj[i][j] ])
				swap(adj[i][0], adj[i][j]);
	}
	bd(1, 1);
	for(int i=1; i<=n-1; i++){
		if(dep[ u[i] ] > dep[ v[i] ]) swap(u[i], v[i]);
	}

	vector<int> cc; cc.pb(-1);
	for(int i=1; i<=m; i++){
		cin>>idx[i]>>co[i];
		cc.pb(co[i]);
	}
	sort(cc.begin(), cc.end()); 
	cc.resize(unique(cc.begin(), cc.end())-cc.begin());
	int siz = cc.size()-1;

	vector<pii> edge; edge.pb({-1,-1});
	for(int i=1; i<=m; i++){
		co[i] = lower_bound(cc.begin(), cc.end(), co[i])-cc.begin(); 
		edge.pb({co[i], idx[i]});
	}
	sort(edge.begin(), edge.end());

	for(int i=1; i<=q; i++){
		cin>>s[i]>>t[i]>>x[i]>>y[i];

		cek[(siz+1)/2].pb({1, siz, i});
	}
	
	// build point
	for(int i=1; i<=m; i++){
		int id = edge[i].se; // idx dr edge
		id = v[id]; // idx dr node
		int cost = cc[ edge[i].fi ];
		// cout << id << ' ' << cost << " cost\n";
		A.upd(tim[id], pii(cost, 1) );
	}
	// cout << GET(tim[6], tim[1]).se << " edge\n";
	// cout << "here\n";
	for(int i=1; i<=q; i++){
		int up = s[i], dw = t[i];
		// cout << up << ' ' << dw << " up\n";
		pii ret = hld(up, dw);

		point[i] = ret.se; // lewat brp edge
		// cout << i << ' ' << point[i] << " pp\n\n";
	}
	bool done = 0;
	while(!done){
		done = 1; A.bd();

		int edupd = 1; // edge ter yg blm update
		for(int i=1; i<=siz; i++){
			// masukin yg costnya = cc[i], cost of unique edge
			while(edupd<edge.size() && edge[edupd].fi == i){
				int id = edge[edupd].se; // idx dr edge
				id = v[id];
				A.upd(tim[id], pii(cc[i], 1) );
				edupd++;
			}
			// cout << "masulk\n";
			// solve cek(i)
			for(auto pp : cek[i]){
				auto [l, r, qidx] = pp;
				int silv = y[qidx];

				int up = s[qidx], dw = t[qidx];
				pii ret = hld(up, dw);
				// silver, num edge

				if(ret.fi <= silv){ // oh bisa 
					cnt[qidx][0] = i; cnt[qidx][1] = ret.fi; 
					cnt[qidx][2] = ret.se;

					int mid = (i+1+r)>>1;
					if(i+1<=r){
						cek[mid].pb({i+1, r, qidx}); done = 0;
					}

				} else {
					int mid = (l+i-1)>>1;
					if(l<=i-1){
						cek[mid].pb({l, i-1, qidx}); done = 0;
					}
				}
			}

			cek[i].clear();
		}
	}
	// cout << siz << " unique cost\n";
	for(int i=1; i<=q; i++){ // punya y[i]
		// cout << i << " i\n";
		// cout << cnt[i][0] << ' '<< cnt[i][1] << ' ' << cnt[i][2] << " cnt\n\n";
		int ed = cnt[i][2];
		if(cnt[i][0]+1 <= siz){
			int sis = y[i]-cnt[i][1];
			ed += sis/cc[ cnt[i][0]+1 ]; // bisa ambil segini lagi
		}

		int gold = point[i]-ed;

		cout << (gold > x[i] ? -1 : x[i]-gold) << '\n'; 
	}
}

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