oj.uz

Submission #761863

# Submission time Handle Problem Language Result Execution time Memory
761863 2023-06-20T10:37:20 Z sentheta Two Currencies (JOI23_currencies) C++17
100 / 100
 2072 ms 80732 KB 
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}












const int N = 1e5+5;
const int LN = 18;

int n, m, q;

pii edg[N];
V<int> adj[N];

int root;

// regular euler tour
int dep[N], in[N], out[N], tim=1;
void dfs_init(int x=root,int par=0){
	in[x] = tim++;
	for(int y : adj[x]) if(y!=par){
		dep[y] = dep[x]+1;
		dfs_init(y, x);
	}
	out[x] = tim-1;
}

// lca sparse table
// duplicated euler tour
int getMinDepth(int x,int y){
	return (dep[x]<dep[y]) ? x : y;
}
struct Stable{
	int v[2*N][LN];
	void build(){
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<2*N; i++){
			v[i][lg] = getMinDepth(v[i][lg-1], v[i+(1<<(lg-1))][lg-1]);
		}
	}
	int qry(int l,int r){
		int lg = __lg(r-l+1);
		return getMinDepth(v[l][lg], v[r-(1<<lg)+1][lg]);
	}
} stable;
int st[N], stim=1;
int getLca(int x,int y){
	if(!(st[x]<st[y])) swap(x,y);
	return stable.qry(st[x], st[y]);
}
void dfs_stable(int x=root,int par=0){
	st[x] = stim;
	stable.v[stim++][0] = x;
	for(int y : adj[x]) if(y!=par){
		dfs_stable(y, x);
		stable.v[stim++][0] = x;
	}
}

// fenwick tree, range update, point query
struct Fenw{
	// int v[N];
	// void reset(){
	// 	rep(i,0,N) v[i] = 0;
	// }
	// void upd(int l,int r,int val){
	// 	for(l++; l<N; l+=l&-l) v[l]+=val;
	// 	r++;
	// 	for(r++; r<N; r+=r&-r) v[r]-=val;
	// }
	// int qry(int i){
	// 	int ret = 0;
	// 	for(i++; i; i-=i&-i) ret+=v[i];
	// 	return ret;
	// }

	#define lc (v+1)
	#define rc (v+2*(mid-tl+1))
	#define mid (tl+tr)/2
	int lz[2*N];
	void reset(){
		rep(v,0,2*N) lz[v] = 0;
	}
	void upd(int l,int r,int val,int v=0,int tl=1,int tr=n){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			lz[v] += val; return;
		}
		upd(l,r,val, lc,tl,mid);
		upd(l,r,val, rc,mid+1,tr);
	}
	int qry(int i,int v=0,int tl=1,int tr=n){
		if(tl==tr) return lz[v];
		if(i<=mid) return lz[v] + qry(i, lc,tl,mid);
		else return lz[v] + qry(i, rc,mid+1,tr);
	}

	int getInPath(int x,int y){
		return qry(in[x]) + qry(in[y]) - 2*qry(in[getLca(x,y)]);
	}
	#undef lc
	#undef rc
	#undef mid
} counter, silver;


// tax position and cost
int pos[N], c[N];

// queries	
int qs[N], qt[N], qx[N], qy[N];
// max #taxes paid by silver
int qans[N];
// range to check
int ql[N], qr[N];
// queries to check
V<int> tochk[N];

void solve(){
	
	cin >> n >> m >> q;
	
	// input edges
	rep(e,1,n){
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
		edg[e] = {u,v};
	}

	root = rng()%n+1;
	dfs_init();
	assert(tim-1==n);

	dfs_stable();
	assert(stim-1==2*n-1);
	stable.build();
	// rep(i,1,n+1) assert(getLca(i,i)==i);
	
	// input taxes
	V<int> txord;
	rep(i,0,m){
		cin >> pos[i] >> c[i];

		txord.push_back(i);

		// put this tax at child
		auto[u,v] = edg[pos[i]];
		pos[i] = u ^ v ^ getMinDepth(u,v);
	}
	sort(all(txord),[&](int i,int j){
		return c[i] < c[j];
	});
	
	// input queries
	rep(i,1,q+1){
		cin >> qs[i] >> qt[i] >> qx[i] >> qy[i];

		qans[i] = 0;
		ql[i] = 0; qr[i] = m-1;
	}

	// silver.getInPath(1,2);
	// return;


	// parallel binsearch
	while(1){
	// rep(loop,0,LN){
		// dbg(loop);

		bool unsolved = 0;
		rep(i,0,m) tochk[i].clear();
		rep(i,1,q+1) if(ql[i]<=qr[i]){
			tochk[(ql[i]+qr[i])/2].push_back(i);
			unsolved = 1;
		}
		if(!unsolved) break;

		counter.reset();
		silver.reset();

		// insert taxes
		rep(i,0,m){
			// dbg(i);

			// insert tax into euler tour
			int idx = txord[i]; // tax ID
			int x = pos[idx];
			counter.upd(in[x], out[x], 1);
			silver.upd(in[x], out[x], c[idx]);

			// check queries
			for(int j : tochk[i]){
				// check whether have enough silver
				if(silver.getInPath(qs[j],qt[j]) <= qy[j]){
					qans[j] = counter.getInPath(qs[j],qt[j]);
					ql[j] = i+1;
				}
				else{
					qr[j] = i-1;
				}
			}
		}

	}

	counter.reset();
	rep(idx,0,m){
		int x = pos[idx];
		counter.upd(in[x], out[x], 1);
	}

	// output answer
	rep(i,1,q+1){
		int ans = qx[i]+qans[i] - counter.getInPath(qs[i],qt[i]);
		ans = max(ans, -1LL);
		cout << ans << nl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36344 KB Output is correct
2 Correct 59 ms 36292 KB Output is correct
3 Correct 56 ms 36400 KB Output is correct
4 Correct 45 ms 36300 KB Output is correct
5 Correct 56 ms 36876 KB Output is correct
6 Correct 57 ms 36968 KB Output is correct
7 Correct 55 ms 36884 KB Output is correct
8 Correct 59 ms 37064 KB Output is correct
9 Correct 56 ms 37080 KB Output is correct
10 Correct 59 ms 37080 KB Output is correct
11 Correct 54 ms 37056 KB Output is correct
12 Correct 55 ms 37064 KB Output is correct
13 Correct 55 ms 37124 KB Output is correct
14 Correct 57 ms 37136 KB Output is correct
15 Correct 60 ms 37064 KB Output is correct
16 Correct 57 ms 37068 KB Output is correct
17 Correct 57 ms 37048 KB Output is correct
18 Correct 65 ms 37092 KB Output is correct
19 Correct 58 ms 37060 KB Output is correct
20 Correct 55 ms 37040 KB Output is correct
21 Correct 56 ms 37068 KB Output is correct
22 Correct 54 ms 37096 KB Output is correct
23 Correct 53 ms 37076 KB Output is correct
24 Correct 52 ms 37088 KB Output is correct
25 Correct 51 ms 37052 KB Output is correct
26 Correct 50 ms 37060 KB Output is correct
27 Correct 50 ms 37060 KB Output is correct
28 Correct 50 ms 37068 KB Output is correct
29 Correct 51 ms 36920 KB Output is correct
30 Correct 55 ms 36948 KB Output is correct
31 Correct 55 ms 37048 KB Output is correct
32 Correct 55 ms 37044 KB Output is correct
33 Correct 55 ms 37124 KB Output is correct
34 Correct 57 ms 37044 KB Output is correct
35 Correct 63 ms 37032 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36300 KB Output is correct
2 Correct 54 ms 37068 KB Output is correct
3 Correct 56 ms 37056 KB Output is correct
4 Correct 66 ms 37104 KB Output is correct
5 Correct 1142 ms 65456 KB Output is correct
6 Correct 1344 ms 71504 KB Output is correct
7 Correct 1285 ms 70100 KB Output is correct
8 Correct 991 ms 64060 KB Output is correct
9 Correct 1002 ms 63384 KB Output is correct
10 Correct 1633 ms 76112 KB Output is correct
11 Correct 1519 ms 76144 KB Output is correct
12 Correct 1556 ms 76112 KB Output is correct
13 Correct 1547 ms 75744 KB Output is correct
14 Correct 1580 ms 76252 KB Output is correct
15 Correct 1879 ms 78952 KB Output is correct
16 Correct 1774 ms 78588 KB Output is correct
17 Correct 2072 ms 79804 KB Output is correct
18 Correct 1816 ms 76056 KB Output is correct
19 Correct 1896 ms 75940 KB Output is correct
20 Correct 1856 ms 75940 KB Output is correct
21 Correct 1641 ms 76072 KB Output is correct
22 Correct 1712 ms 76104 KB Output is correct
23 Correct 1531 ms 76148 KB Output is correct
24 Correct 1585 ms 76224 KB Output is correct
25 Correct 1187 ms 76204 KB Output is correct
26 Correct 1154 ms 75808 KB Output is correct
27 Correct 1181 ms 76760 KB Output is correct
28 Correct 874 ms 74844 KB Output is correct
29 Correct 871 ms 73576 KB Output is correct
30 Correct 937 ms 73536 KB Output is correct
31 Correct 922 ms 73520 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36324 KB Output is correct
2 Correct 56 ms 37088 KB Output is correct
3 Correct 56 ms 37024 KB Output is correct
4 Correct 59 ms 37128 KB Output is correct
5 Correct 1155 ms 68104 KB Output is correct
6 Correct 1045 ms 68564 KB Output is correct
7 Correct 1445 ms 69960 KB Output is correct
8 Correct 1791 ms 79020 KB Output is correct
9 Correct 1940 ms 80600 KB Output is correct
10 Correct 1813 ms 80732 KB Output is correct
11 Correct 1317 ms 79188 KB Output is correct
12 Correct 1351 ms 79292 KB Output is correct
13 Correct 1347 ms 79268 KB Output is correct
14 Correct 1024 ms 79092 KB Output is correct
15 Correct 896 ms 80316 KB Output is correct
16 Correct 1058 ms 79960 KB Output is correct
17 Correct 1072 ms 78468 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36344 KB Output is correct
2 Correct 59 ms 36292 KB Output is correct
3 Correct 56 ms 36400 KB Output is correct
4 Correct 45 ms 36300 KB Output is correct
5 Correct 56 ms 36876 KB Output is correct
6 Correct 57 ms 36968 KB Output is correct
7 Correct 55 ms 36884 KB Output is correct
8 Correct 59 ms 37064 KB Output is correct
9 Correct 56 ms 37080 KB Output is correct
10 Correct 59 ms 37080 KB Output is correct
11 Correct 54 ms 37056 KB Output is correct
12 Correct 55 ms 37064 KB Output is correct
13 Correct 55 ms 37124 KB Output is correct
14 Correct 57 ms 37136 KB Output is correct
15 Correct 60 ms 37064 KB Output is correct
16 Correct 57 ms 37068 KB Output is correct
17 Correct 57 ms 37048 KB Output is correct
18 Correct 65 ms 37092 KB Output is correct
19 Correct 58 ms 37060 KB Output is correct
20 Correct 55 ms 37040 KB Output is correct
21 Correct 56 ms 37068 KB Output is correct
22 Correct 54 ms 37096 KB Output is correct
23 Correct 53 ms 37076 KB Output is correct
24 Correct 52 ms 37088 KB Output is correct
25 Correct 51 ms 37052 KB Output is correct
26 Correct 50 ms 37060 KB Output is correct
27 Correct 50 ms 37060 KB Output is correct
28 Correct 50 ms 37068 KB Output is correct
29 Correct 51 ms 36920 KB Output is correct
30 Correct 55 ms 36948 KB Output is correct
31 Correct 55 ms 37048 KB Output is correct
32 Correct 55 ms 37044 KB Output is correct
33 Correct 55 ms 37124 KB Output is correct
34 Correct 57 ms 37044 KB Output is correct
35 Correct 63 ms 37032 KB Output is correct
36 Correct 40 ms 36300 KB Output is correct
37 Correct 54 ms 37068 KB Output is correct
38 Correct 56 ms 37056 KB Output is correct
39 Correct 66 ms 37104 KB Output is correct
40 Correct 1142 ms 65456 KB Output is correct
41 Correct 1344 ms 71504 KB Output is correct
42 Correct 1285 ms 70100 KB Output is correct
43 Correct 991 ms 64060 KB Output is correct
44 Correct 1002 ms 63384 KB Output is correct
45 Correct 1633 ms 76112 KB Output is correct
46 Correct 1519 ms 76144 KB Output is correct
47 Correct 1556 ms 76112 KB Output is correct
48 Correct 1547 ms 75744 KB Output is correct
49 Correct 1580 ms 76252 KB Output is correct
50 Correct 1879 ms 78952 KB Output is correct
51 Correct 1774 ms 78588 KB Output is correct
52 Correct 2072 ms 79804 KB Output is correct
53 Correct 1816 ms 76056 KB Output is correct
54 Correct 1896 ms 75940 KB Output is correct
55 Correct 1856 ms 75940 KB Output is correct
56 Correct 1641 ms 76072 KB Output is correct
57 Correct 1712 ms 76104 KB Output is correct
58 Correct 1531 ms 76148 KB Output is correct
59 Correct 1585 ms 76224 KB Output is correct
60 Correct 1187 ms 76204 KB Output is correct
61 Correct 1154 ms 75808 KB Output is correct
62 Correct 1181 ms 76760 KB Output is correct
63 Correct 874 ms 74844 KB Output is correct
64 Correct 871 ms 73576 KB Output is correct
65 Correct 937 ms 73536 KB Output is correct
66 Correct 922 ms 73520 KB Output is correct
67 Correct 41 ms 36324 KB Output is correct
68 Correct 56 ms 37088 KB Output is correct
69 Correct 56 ms 37024 KB Output is correct
70 Correct 59 ms 37128 KB Output is correct
71 Correct 1155 ms 68104 KB Output is correct
72 Correct 1045 ms 68564 KB Output is correct
73 Correct 1445 ms 69960 KB Output is correct
74 Correct 1791 ms 79020 KB Output is correct
75 Correct 1940 ms 80600 KB Output is correct
76 Correct 1813 ms 80732 KB Output is correct
77 Correct 1317 ms 79188 KB Output is correct
78 Correct 1351 ms 79292 KB Output is correct
79 Correct 1347 ms 79268 KB Output is correct
80 Correct 1024 ms 79092 KB Output is correct
81 Correct 896 ms 80316 KB Output is correct
82 Correct 1058 ms 79960 KB Output is correct
83 Correct 1072 ms 78468 KB Output is correct
84 Correct 1216 ms 64804 KB Output is correct
85 Correct 1152 ms 64716 KB Output is correct
86 Correct 987 ms 63412 KB Output is correct
87 Correct 1633 ms 76088 KB Output is correct
88 Correct 1596 ms 75900 KB Output is correct
89 Correct 1645 ms 76012 KB Output is correct
90 Correct 1620 ms 76116 KB Output is correct
91 Correct 1601 ms 76076 KB Output is correct
92 Correct 1894 ms 79832 KB Output is correct
93 Correct 1897 ms 79052 KB Output is correct
94 Correct 1771 ms 75964 KB Output is correct
95 Correct 1851 ms 76032 KB Output is correct
96 Correct 1843 ms 75944 KB Output is correct
97 Correct 1843 ms 75908 KB Output is correct
98 Correct 1594 ms 76168 KB Output is correct
99 Correct 1640 ms 75768 KB Output is correct
100 Correct 1612 ms 76280 KB Output is correct
101 Correct 1624 ms 76368 KB Output is correct
102 Correct 1291 ms 76348 KB Output is correct
103 Correct 1272 ms 76508 KB Output is correct
104 Correct 1170 ms 76472 KB Output is correct
105 Correct 904 ms 73064 KB Output is correct
106 Correct 891 ms 74644 KB Output is correct
107 Correct 972 ms 72952 KB Output is correct
108 Correct 970 ms 73148 KB Output is correct