oj.uz

Submission #976943

# Submission time Handle Problem Language Result Execution time Memory
976943 2024-05-07T09:28:06 Z TomkeMonke Two Currencies (JOI23_currencies) C++17
100 / 100
 1216 ms 67016 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
 
 
const int MAXN = 1e5 + 7;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const int base = 1<<18;
const int LOG = 18;
const int A = 26;
const int PROD = 2 * MAXN;
const int MAX = 2e3 + 7;
const int SQ = 220;

struct interval {
	
	int lo, hi, mid;
};

vector<pair<int, int>> G[MAXN];
vector<int> mids[MAXN];
pair<int, int> checkpoints[MAXN];
tuple<int, int, int, int> que[MAXN];
pii tree[2 * base];
int queriesLCA[MAXN];
int pre[MAXN], post[MAXN];
int jmp[MAXN][LOG];
int edges[MAXN];
int depth[MAXN];
int ans[MAXN];
interval bin[MAXN];
int c = 0;
int n, m, q;


void update(int v, pair<int, int> val){
	
	v += base;
	tree[v].fi += val.fi;
	tree[v].se += val.se;
	v /= 2;
	
	while(v > 0){
		
		tree[v] = {tree[2 * v].fi + tree[2 * v + 1].fi, tree[2 * v].se + tree[2 * v + 1].se};
		v /= 2;	
	}
}


pair<int, int> query(int a, int b){
	
	a += base - 1;
	b += base + 1;
	
	pair<int, int> res = {0, 0};
	
	while(a/2 != b/2){
		
		if(a%2 == 0){
			
			res.fi += tree[a + 1].fi;
			res.se += tree[a + 1].se;
		}
		
		if(b%2 == 1){
			
			res.fi += tree[b - 1].fi;
			res.se += tree[b - 1].se;
		}
		
		a /= 2; b /= 2;
	}
	
	return res;
}


void DFS(int v, int p){
	
	depth[v] = depth[p] + 1;
	pre[v] = ++c;
	jmp[v][0] = p;
	
	for(int j = 1; j < LOG; j++){
		
		jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
	}
	
	for(auto [u, ind] : G[v]){
		
		if(u == p) continue;
		edges[ind] = u;
		DFS(u, v);
	}
	
	post[v] = ++c;
}


int lca(int u, int v){
	
	if(depth[u] < depth[v]) swap(u, v);
	int diff = depth[u] - depth[v];
	
	for(int i = 0; i < LOG; i++){
    	
        if((1<<i) & diff){
        	
        	u = jmp[u][i];
		}
    }
	
	if(u == v) return u;
	
	for(int i = LOG - 1; i >= 0; i--){
		
		if(jmp[u][i] != jmp[v][i]){
			
			u = jmp[u][i];
			v = jmp[v][i];
		}
	}
	
	return jmp[v][0];
}


void treeclear(){
	
	for(int i = 0; i < 2 * base; i++){
		
		tree[i] = {0, 0};
	}
}

bool check(tuple<int, int, int, int> a, int v){
	
	auto [s, t, x, y] = a;
	
	if(depth[t] < depth[s]) swap(s, t);
	
	pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.fi -= tree[pre[queriesLCA[v]] + base].fi;
	res.se -= tree[pre[queriesLCA[v]] + base].se;
	
	if(queriesLCA[v] != s){
		
		pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
		x.fi -= tree[pre[queriesLCA[v]] + base].fi;
		x.se -= tree[pre[queriesLCA[v]] + base].se;
		
		res.fi += x.fi;
		res.se += x.se;
	}
	
	return res.fi <= y;
}



void parallel_binsearch(){
	
	int left = q;
	
	while(left){
		
		for(int i = 0; i <= m; i++){
		
			update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
			update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
			
			for(auto cand : mids[i]){
				
				if(check(que[cand], cand)) bin[cand].lo = i + 1;
				else bin[cand].hi = i;
				
				bin[cand].mid = (bin[cand].lo + bin[cand].hi)/2;
				
				if(bin[cand].lo == bin[cand].hi) left--;
				else mids[bin[cand].mid].push_back(cand);
			}
			
			mids[i].clear();
		}
		
		treeclear();
	}
}


void save_res(int v, bool save){
	
	auto [s, t, x, y] = que[v];
	
	if(depth[t] < depth[s]) swap(s, t);
	
	pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
	res.fi -= tree[pre[queriesLCA[v]] + base].fi;
	res.se -= tree[pre[queriesLCA[v]] + base].se;
	
	if(queriesLCA[v] != s){
		
		pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
		x.fi -= tree[pre[queriesLCA[v]] + base].fi;
		x.se -= tree[pre[queriesLCA[v]] + base].se;
		
		res.fi += x.fi;
		res.se += x.se;
	}
	
	if(save){
		
		ans[v] = res.se;
		if(res.fi > y) ans[v] = max(ans[v] - 1, 0LL);
	}
	
	else ans[v] = x - max(0LL, res.se - ans[v]);
}




void rozw(){
	
	for(int i = 1; i <= q; i++){
		
		mids[bin[i].lo].push_back(i);
	}
	
	for(int i = 0; i <= m; i++){
		
		update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
		update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
		
		for(auto cand : mids[i]){
			
			save_res(cand, 1);
		}
		
		mids[i].clear();
	}
	
	for(int i = 1; i <= q; i++){
	
		save_res(i, 0);
	}
}



void solve(){
	
	cin >> n >> m >> q;
	
	for(int i = 1; i < n; i++){
		
		int a, b;
		cin >> a >> b;
		G[a].push_back({b, i});
		G[b].push_back({a, i});
	}
	
	for(int i = 1; i <= m; i++){
		
		int p, c;
		cin >> p >> c;
		checkpoints[i] = {c, p};
	}
	
	DFS(1, 1);
	
	for(int i = 1; i <= q; i++){
		
		int s, t, x, y;
		cin >> s >> t >> x >> y;
		
		que[i] = {s, t, x, y};
		queriesLCA[i] = lca(s, t);
		bin[i].lo = 0;
		bin[i].hi = m;
		bin[i].mid = m/2;
		mids[bin[i].mid].push_back(i);
	}
	
	sort(checkpoints + 1, checkpoints + m + 1);
	parallel_binsearch();
	rozw();
	
	for(int i = 1; i <= q; i++){
		
		cout << max(ans[i], -1LL) << '\n';
	}	
}

bool multi = 0;
 
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int t = 1;
	if(multi) cin >> t;
	
	while(t--) solve();
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22616 KB Output is correct
2 Correct 6 ms 22360 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 5 ms 22620 KB Output is correct
5 Correct 14 ms 22876 KB Output is correct
6 Correct 15 ms 22872 KB Output is correct
7 Correct 14 ms 23128 KB Output is correct
8 Correct 16 ms 22872 KB Output is correct
9 Correct 17 ms 22876 KB Output is correct
10 Correct 18 ms 23384 KB Output is correct
11 Correct 16 ms 22872 KB Output is correct
12 Correct 16 ms 22876 KB Output is correct
13 Correct 15 ms 23132 KB Output is correct
14 Correct 15 ms 23132 KB Output is correct
15 Correct 15 ms 23032 KB Output is correct
16 Correct 16 ms 23064 KB Output is correct
17 Correct 16 ms 22872 KB Output is correct
18 Correct 15 ms 22876 KB Output is correct
19 Correct 16 ms 23040 KB Output is correct
20 Correct 14 ms 22872 KB Output is correct
21 Correct 19 ms 22872 KB Output is correct
22 Correct 15 ms 22876 KB Output is correct
23 Correct 14 ms 22876 KB Output is correct
24 Correct 15 ms 22876 KB Output is correct
25 Correct 15 ms 23128 KB Output is correct
26 Correct 13 ms 22876 KB Output is correct
27 Correct 11 ms 22872 KB Output is correct
28 Correct 13 ms 22876 KB Output is correct
29 Correct 12 ms 22796 KB Output is correct
30 Correct 15 ms 22872 KB Output is correct
31 Correct 18 ms 23132 KB Output is correct
32 Correct 15 ms 22872 KB Output is correct
33 Correct 14 ms 23132 KB Output is correct
34 Correct 15 ms 23132 KB Output is correct
35 Correct 14 ms 23132 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 17 ms 23128 KB Output is correct
3 Correct 15 ms 22876 KB Output is correct
4 Correct 15 ms 22876 KB Output is correct
5 Correct 675 ms 54776 KB Output is correct
6 Correct 823 ms 55224 KB Output is correct
7 Correct 739 ms 56424 KB Output is correct
8 Correct 589 ms 54564 KB Output is correct
9 Correct 579 ms 53672 KB Output is correct
10 Correct 1155 ms 62272 KB Output is correct
11 Correct 992 ms 62712 KB Output is correct
12 Correct 993 ms 62148 KB Output is correct
13 Correct 1016 ms 62312 KB Output is correct
14 Correct 1008 ms 62232 KB Output is correct
15 Correct 941 ms 66736 KB Output is correct
16 Correct 940 ms 66852 KB Output is correct
17 Correct 930 ms 66500 KB Output is correct
18 Correct 1129 ms 62676 KB Output is correct
19 Correct 1094 ms 62492 KB Output is correct
20 Correct 1119 ms 62460 KB Output is correct
21 Correct 789 ms 63212 KB Output is correct
22 Correct 789 ms 62984 KB Output is correct
23 Correct 813 ms 62820 KB Output is correct
24 Correct 811 ms 62868 KB Output is correct
25 Correct 793 ms 62096 KB Output is correct
26 Correct 800 ms 61592 KB Output is correct
27 Correct 795 ms 61744 KB Output is correct
28 Correct 469 ms 60172 KB Output is correct
29 Correct 452 ms 59044 KB Output is correct
30 Correct 578 ms 59460 KB Output is correct
31 Correct 626 ms 59364 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22620 KB Output is correct
2 Correct 15 ms 23116 KB Output is correct
3 Correct 16 ms 23128 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 559 ms 59048 KB Output is correct
6 Correct 541 ms 59336 KB Output is correct
7 Correct 660 ms 52812 KB Output is correct
8 Correct 961 ms 66612 KB Output is correct
9 Correct 1037 ms 66832 KB Output is correct
10 Correct 1014 ms 66772 KB Output is correct
11 Correct 820 ms 66860 KB Output is correct
12 Correct 814 ms 67016 KB Output is correct
13 Correct 788 ms 66724 KB Output is correct
14 Correct 689 ms 66500 KB Output is correct
15 Correct 628 ms 66508 KB Output is correct
16 Correct 755 ms 66752 KB Output is correct
17 Correct 711 ms 66756 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22616 KB Output is correct
2 Correct 6 ms 22360 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 5 ms 22620 KB Output is correct
5 Correct 14 ms 22876 KB Output is correct
6 Correct 15 ms 22872 KB Output is correct
7 Correct 14 ms 23128 KB Output is correct
8 Correct 16 ms 22872 KB Output is correct
9 Correct 17 ms 22876 KB Output is correct
10 Correct 18 ms 23384 KB Output is correct
11 Correct 16 ms 22872 KB Output is correct
12 Correct 16 ms 22876 KB Output is correct
13 Correct 15 ms 23132 KB Output is correct
14 Correct 15 ms 23132 KB Output is correct
15 Correct 15 ms 23032 KB Output is correct
16 Correct 16 ms 23064 KB Output is correct
17 Correct 16 ms 22872 KB Output is correct
18 Correct 15 ms 22876 KB Output is correct
19 Correct 16 ms 23040 KB Output is correct
20 Correct 14 ms 22872 KB Output is correct
21 Correct 19 ms 22872 KB Output is correct
22 Correct 15 ms 22876 KB Output is correct
23 Correct 14 ms 22876 KB Output is correct
24 Correct 15 ms 22876 KB Output is correct
25 Correct 15 ms 23128 KB Output is correct
26 Correct 13 ms 22876 KB Output is correct
27 Correct 11 ms 22872 KB Output is correct
28 Correct 13 ms 22876 KB Output is correct
29 Correct 12 ms 22796 KB Output is correct
30 Correct 15 ms 22872 KB Output is correct
31 Correct 18 ms 23132 KB Output is correct
32 Correct 15 ms 22872 KB Output is correct
33 Correct 14 ms 23132 KB Output is correct
34 Correct 15 ms 23132 KB Output is correct
35 Correct 14 ms 23132 KB Output is correct
36 Correct 5 ms 22620 KB Output is correct
37 Correct 17 ms 23128 KB Output is correct
38 Correct 15 ms 22876 KB Output is correct
39 Correct 15 ms 22876 KB Output is correct
40 Correct 675 ms 54776 KB Output is correct
41 Correct 823 ms 55224 KB Output is correct
42 Correct 739 ms 56424 KB Output is correct
43 Correct 589 ms 54564 KB Output is correct
44 Correct 579 ms 53672 KB Output is correct
45 Correct 1155 ms 62272 KB Output is correct
46 Correct 992 ms 62712 KB Output is correct
47 Correct 993 ms 62148 KB Output is correct
48 Correct 1016 ms 62312 KB Output is correct
49 Correct 1008 ms 62232 KB Output is correct
50 Correct 941 ms 66736 KB Output is correct
51 Correct 940 ms 66852 KB Output is correct
52 Correct 930 ms 66500 KB Output is correct
53 Correct 1129 ms 62676 KB Output is correct
54 Correct 1094 ms 62492 KB Output is correct
55 Correct 1119 ms 62460 KB Output is correct
56 Correct 789 ms 63212 KB Output is correct
57 Correct 789 ms 62984 KB Output is correct
58 Correct 813 ms 62820 KB Output is correct
59 Correct 811 ms 62868 KB Output is correct
60 Correct 793 ms 62096 KB Output is correct
61 Correct 800 ms 61592 KB Output is correct
62 Correct 795 ms 61744 KB Output is correct
63 Correct 469 ms 60172 KB Output is correct
64 Correct 452 ms 59044 KB Output is correct
65 Correct 578 ms 59460 KB Output is correct
66 Correct 626 ms 59364 KB Output is correct
67 Correct 4 ms 22620 KB Output is correct
68 Correct 15 ms 23116 KB Output is correct
69 Correct 16 ms 23128 KB Output is correct
70 Correct 14 ms 23128 KB Output is correct
71 Correct 559 ms 59048 KB Output is correct
72 Correct 541 ms 59336 KB Output is correct
73 Correct 660 ms 52812 KB Output is correct
74 Correct 961 ms 66612 KB Output is correct
75 Correct 1037 ms 66832 KB Output is correct
76 Correct 1014 ms 66772 KB Output is correct
77 Correct 820 ms 66860 KB Output is correct
78 Correct 814 ms 67016 KB Output is correct
79 Correct 788 ms 66724 KB Output is correct
80 Correct 689 ms 66500 KB Output is correct
81 Correct 628 ms 66508 KB Output is correct
82 Correct 755 ms 66752 KB Output is correct
83 Correct 711 ms 66756 KB Output is correct
84 Correct 713 ms 52432 KB Output is correct
85 Correct 669 ms 48584 KB Output is correct
86 Correct 594 ms 48088 KB Output is correct
87 Correct 1089 ms 62468 KB Output is correct
88 Correct 1131 ms 62396 KB Output is correct
89 Correct 1077 ms 62156 KB Output is correct
90 Correct 1090 ms 62644 KB Output is correct
91 Correct 1119 ms 62524 KB Output is correct
92 Correct 1096 ms 65140 KB Output is correct
93 Correct 1079 ms 66060 KB Output is correct
94 Correct 1163 ms 62464 KB Output is correct
95 Correct 1216 ms 62984 KB Output is correct
96 Correct 1196 ms 62480 KB Output is correct
97 Correct 1177 ms 62540 KB Output is correct
98 Correct 1010 ms 62540 KB Output is correct
99 Correct 970 ms 62412 KB Output is correct
100 Correct 971 ms 62652 KB Output is correct
101 Correct 942 ms 62612 KB Output is correct
102 Correct 910 ms 62484 KB Output is correct
103 Correct 866 ms 62920 KB Output is correct
104 Correct 865 ms 62632 KB Output is correct
105 Correct 550 ms 59216 KB Output is correct
106 Correct 549 ms 59772 KB Output is correct
107 Correct 673 ms 59108 KB Output is correct
108 Correct 747 ms 59344 KB Output is correct