oj.uz

Submission #743500

# Submission time Handle Problem Language Result Execution time Memory
743500 2023-05-17T12:43:06 Z emptypringlescan Two Currencies (JOI23_currencies) C++17
100 / 100
 1138 ms 469160 KB 
#include <bits/stdc++.h>
using namespace std;
struct node{
	long long val,cnt;
	node *l, *r;
	node(long long V, long long C){
		val=V;
		cnt=C;
		l=r=NULL;
	}
	node(node* le, node* ri){
		l=le;
		r=ri;
		val=l->val+r->val;
		cnt=l->cnt+r->cnt;
	}
};

void prop(node* nd){
	if(nd->l==NULL){
		nd->r=new node(0LL,0LL);
		nd->l=new node(0LL,0LL);
	}
}
node* update(node* lol, int s, int e, int x){
	if(s==e) return new node(lol->val+s,lol->cnt+1);
	int mid=(s+e)/2;
	prop(lol);
	if(x<=mid) return new node(update(lol->l,s,mid,x),lol->r);
	else return new node(lol->l,update(lol->r,mid+1,e,x));
}
long long bsta(node* base, node* base2, node* one, node* two, int s, int e, long long V){
	long long tcnt=one->cnt+two->cnt-base->cnt-base2->cnt;
	if(s==e){
		return min(tcnt,V/(long long)s);
	}
	int mid=(s+e)/2;
	prop(base); prop(base2); prop(one); prop(two);
	long long ltcnt=one->l->cnt+two->l->cnt-base->l->cnt-base2->l->cnt;
	long long ltval=one->l->val+two->l->val-base->l->val-base2->l->val;
	if(ltval>V) return bsta(base->l,base2->l,one->l,two->l,s,mid,V);
	else return ltcnt+bsta(base->r,base2->r,one->r,two->r,mid+1,e,V-ltval);
}
node* nodes[200005];
vector<int> adj[200005];
long long cost[200005];
int par[200005];
void dfs(int x, int p){
	nodes[x]=update(nodes[p],0,1000000005,cost[x]);
	for(int i:adj[x]){
		if(i==p) continue;
		par[i]=x;
		dfs(i,x);
	}
}
const int MAXN = 200050;
const int LOGN = 20;
int p[LOGN+1][MAXN], h[MAXN];   //h: number of edges from root
bitset<MAXN> visited;
void dfss(int x) {
    if (visited[x]) return;
    visited[x] = 1LL;
    for (int k = 0LL; k < LOGN; ++k) {
        if (p[k][x] == -1LL) break;
        p[k+1LL][x] = p[k][p[k][x]];
    }
    for (int it:adj[x]) {
        if (visited[it]) continue;
        p[0][it] = x;
        h[it] = h[x] + 1LL;
        dfss(it);
    }
}

/* Query */
int lca(int a, int b) { //h[a] < h[b]
    if (h[a] > h[b]) swap(a, b);
    /* advance b by h[b] - h[a] parents */
    for (int k = 0, d = h[b] - h[a]; k < LOGN; ++k) {
        if (d & (1<<k))  b = p[k][b];
    }
    if (a == b) return a;
    assert(h[a] == h[b]); //same height
    /* to be continued */
    for (int k = LOGN-1; k >= 0; --k) {
        if (p[k][a] != p[k][b]) 
            a = p[k][a], b = p[k][b];
    }
    assert(p[0][a] == p[0][b]);        //same immediate parent
    return p[0][a];
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(p,-1,sizeof(p));
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int> > edges;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		edges.push_back({a,b});
	}
	int cnt=n+1LL;
	for(int i=0; i<m; i++){
		int a;
		long long b;
		cin >> a >> b;
		cost[cnt]=b;
		edges.push_back({cnt,edges[a-1LL].second});
		edges[a-1LL].second=cnt;
		cnt++;
	}
	for(auto i:edges){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	nodes[0]=new node(0LL,0LL);
	dfs(1LL,0LL);
	dfss(1LL);
	for(int i=0; i<q; i++){
		int a,b;
		long long c,d;
		cin >> a >> b >> c >> d;
		int o=lca(a,b);
		int cry=par[o];
		long long yes=bsta(nodes[o],nodes[cry],nodes[a],nodes[b],0,1000000005,d);
		long long ret=c-(h[a]+h[b]-2*h[o]+1-yes);
		if(ret<0) cout << -1 << '\n';
		else cout << ret << '\n';
	}
}
/*5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 11 ms 21460 KB Output is correct
3 Correct 10 ms 21436 KB Output is correct
4 Correct 11 ms 21484 KB Output is correct
5 Correct 24 ms 30424 KB Output is correct
6 Correct 22 ms 30500 KB Output is correct
7 Correct 19 ms 28132 KB Output is correct
8 Correct 23 ms 31224 KB Output is correct
9 Correct 23 ms 31232 KB Output is correct
10 Correct 25 ms 31144 KB Output is correct
11 Correct 22 ms 31188 KB Output is correct
12 Correct 24 ms 31188 KB Output is correct
13 Correct 23 ms 31308 KB Output is correct
14 Correct 24 ms 31372 KB Output is correct
15 Correct 25 ms 31288 KB Output is correct
16 Correct 23 ms 31252 KB Output is correct
17 Correct 29 ms 31180 KB Output is correct
18 Correct 23 ms 31252 KB Output is correct
19 Correct 25 ms 31120 KB Output is correct
20 Correct 25 ms 31184 KB Output is correct
21 Correct 22 ms 31196 KB Output is correct
22 Correct 23 ms 31136 KB Output is correct
23 Correct 22 ms 31184 KB Output is correct
24 Correct 22 ms 31240 KB Output is correct
25 Correct 22 ms 31188 KB Output is correct
26 Correct 21 ms 31188 KB Output is correct
27 Correct 22 ms 31196 KB Output is correct
28 Correct 22 ms 31188 KB Output is correct
29 Correct 21 ms 31188 KB Output is correct
30 Correct 18 ms 27560 KB Output is correct
31 Correct 18 ms 27536 KB Output is correct
32 Correct 18 ms 27604 KB Output is correct
33 Correct 27 ms 31564 KB Output is correct
34 Correct 24 ms 31360 KB Output is correct
35 Correct 24 ms 31464 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21460 KB Output is correct
2 Correct 18 ms 27604 KB Output is correct
3 Correct 16 ms 27556 KB Output is correct
4 Correct 24 ms 27540 KB Output is correct
5 Correct 497 ms 312360 KB Output is correct
6 Correct 487 ms 250212 KB Output is correct
7 Correct 457 ms 248712 KB Output is correct
8 Correct 416 ms 250756 KB Output is correct
9 Correct 416 ms 258088 KB Output is correct
10 Correct 606 ms 328436 KB Output is correct
11 Correct 646 ms 328440 KB Output is correct
12 Correct 608 ms 328484 KB Output is correct
13 Correct 721 ms 328480 KB Output is correct
14 Correct 620 ms 323728 KB Output is correct
15 Correct 743 ms 342200 KB Output is correct
16 Correct 701 ms 342968 KB Output is correct
17 Correct 757 ms 341668 KB Output is correct
18 Correct 697 ms 330508 KB Output is correct
19 Correct 710 ms 330552 KB Output is correct
20 Correct 656 ms 330700 KB Output is correct
21 Correct 548 ms 329488 KB Output is correct
22 Correct 554 ms 329832 KB Output is correct
23 Correct 545 ms 329728 KB Output is correct
24 Correct 525 ms 329720 KB Output is correct
25 Correct 533 ms 333552 KB Output is correct
26 Correct 540 ms 333640 KB Output is correct
27 Correct 727 ms 333552 KB Output is correct
28 Correct 482 ms 325156 KB Output is correct
29 Correct 485 ms 329720 KB Output is correct
30 Correct 484 ms 329996 KB Output is correct
31 Correct 482 ms 330004 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 23 ms 31392 KB Output is correct
3 Correct 24 ms 31416 KB Output is correct
4 Correct 27 ms 31456 KB Output is correct
5 Correct 643 ms 363624 KB Output is correct
6 Correct 601 ms 322260 KB Output is correct
7 Correct 786 ms 375976 KB Output is correct
8 Correct 988 ms 469064 KB Output is correct
9 Correct 1002 ms 469048 KB Output is correct
10 Correct 978 ms 468856 KB Output is correct
11 Correct 892 ms 469036 KB Output is correct
12 Correct 969 ms 468908 KB Output is correct
13 Correct 947 ms 468864 KB Output is correct
14 Correct 842 ms 468788 KB Output is correct
15 Correct 835 ms 468708 KB Output is correct
16 Correct 825 ms 469160 KB Output is correct
17 Correct 839 ms 468832 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 11 ms 21460 KB Output is correct
3 Correct 10 ms 21436 KB Output is correct
4 Correct 11 ms 21484 KB Output is correct
5 Correct 24 ms 30424 KB Output is correct
6 Correct 22 ms 30500 KB Output is correct
7 Correct 19 ms 28132 KB Output is correct
8 Correct 23 ms 31224 KB Output is correct
9 Correct 23 ms 31232 KB Output is correct
10 Correct 25 ms 31144 KB Output is correct
11 Correct 22 ms 31188 KB Output is correct
12 Correct 24 ms 31188 KB Output is correct
13 Correct 23 ms 31308 KB Output is correct
14 Correct 24 ms 31372 KB Output is correct
15 Correct 25 ms 31288 KB Output is correct
16 Correct 23 ms 31252 KB Output is correct
17 Correct 29 ms 31180 KB Output is correct
18 Correct 23 ms 31252 KB Output is correct
19 Correct 25 ms 31120 KB Output is correct
20 Correct 25 ms 31184 KB Output is correct
21 Correct 22 ms 31196 KB Output is correct
22 Correct 23 ms 31136 KB Output is correct
23 Correct 22 ms 31184 KB Output is correct
24 Correct 22 ms 31240 KB Output is correct
25 Correct 22 ms 31188 KB Output is correct
26 Correct 21 ms 31188 KB Output is correct
27 Correct 22 ms 31196 KB Output is correct
28 Correct 22 ms 31188 KB Output is correct
29 Correct 21 ms 31188 KB Output is correct
30 Correct 18 ms 27560 KB Output is correct
31 Correct 18 ms 27536 KB Output is correct
32 Correct 18 ms 27604 KB Output is correct
33 Correct 27 ms 31564 KB Output is correct
34 Correct 24 ms 31360 KB Output is correct
35 Correct 24 ms 31464 KB Output is correct
36 Correct 9 ms 21460 KB Output is correct
37 Correct 18 ms 27604 KB Output is correct
38 Correct 16 ms 27556 KB Output is correct
39 Correct 24 ms 27540 KB Output is correct
40 Correct 497 ms 312360 KB Output is correct
41 Correct 487 ms 250212 KB Output is correct
42 Correct 457 ms 248712 KB Output is correct
43 Correct 416 ms 250756 KB Output is correct
44 Correct 416 ms 258088 KB Output is correct
45 Correct 606 ms 328436 KB Output is correct
46 Correct 646 ms 328440 KB Output is correct
47 Correct 608 ms 328484 KB Output is correct
48 Correct 721 ms 328480 KB Output is correct
49 Correct 620 ms 323728 KB Output is correct
50 Correct 743 ms 342200 KB Output is correct
51 Correct 701 ms 342968 KB Output is correct
52 Correct 757 ms 341668 KB Output is correct
53 Correct 697 ms 330508 KB Output is correct
54 Correct 710 ms 330552 KB Output is correct
55 Correct 656 ms 330700 KB Output is correct
56 Correct 548 ms 329488 KB Output is correct
57 Correct 554 ms 329832 KB Output is correct
58 Correct 545 ms 329728 KB Output is correct
59 Correct 525 ms 329720 KB Output is correct
60 Correct 533 ms 333552 KB Output is correct
61 Correct 540 ms 333640 KB Output is correct
62 Correct 727 ms 333552 KB Output is correct
63 Correct 482 ms 325156 KB Output is correct
64 Correct 485 ms 329720 KB Output is correct
65 Correct 484 ms 329996 KB Output is correct
66 Correct 482 ms 330004 KB Output is correct
67 Correct 10 ms 21460 KB Output is correct
68 Correct 23 ms 31392 KB Output is correct
69 Correct 24 ms 31416 KB Output is correct
70 Correct 27 ms 31456 KB Output is correct
71 Correct 643 ms 363624 KB Output is correct
72 Correct 601 ms 322260 KB Output is correct
73 Correct 786 ms 375976 KB Output is correct
74 Correct 988 ms 469064 KB Output is correct
75 Correct 1002 ms 469048 KB Output is correct
76 Correct 978 ms 468856 KB Output is correct
77 Correct 892 ms 469036 KB Output is correct
78 Correct 969 ms 468908 KB Output is correct
79 Correct 947 ms 468864 KB Output is correct
80 Correct 842 ms 468788 KB Output is correct
81 Correct 835 ms 468708 KB Output is correct
82 Correct 825 ms 469160 KB Output is correct
83 Correct 839 ms 468832 KB Output is correct
84 Correct 694 ms 411528 KB Output is correct
85 Correct 611 ms 343756 KB Output is correct
86 Correct 529 ms 271852 KB Output is correct
87 Correct 836 ms 455628 KB Output is correct
88 Correct 870 ms 455500 KB Output is correct
89 Correct 861 ms 455720 KB Output is correct
90 Correct 928 ms 455712 KB Output is correct
91 Correct 865 ms 455548 KB Output is correct
92 Correct 1138 ms 464188 KB Output is correct
93 Correct 1109 ms 466888 KB Output is correct
94 Correct 1016 ms 456444 KB Output is correct
95 Correct 1038 ms 456452 KB Output is correct
96 Correct 1055 ms 456212 KB Output is correct
97 Correct 1035 ms 456364 KB Output is correct
98 Correct 889 ms 455408 KB Output is correct
99 Correct 783 ms 455652 KB Output is correct
100 Correct 820 ms 455396 KB Output is correct
101 Correct 771 ms 455616 KB Output is correct
102 Correct 865 ms 459132 KB Output is correct
103 Correct 845 ms 459044 KB Output is correct
104 Correct 826 ms 459000 KB Output is correct
105 Correct 663 ms 455744 KB Output is correct
106 Correct 671 ms 455764 KB Output is correct
107 Correct 679 ms 455544 KB Output is correct
108 Correct 693 ms 455748 KB Output is correct