oj.uz

Submission #970929

# Submission time Handle Problem Language Result Execution time Memory
970929 2024-04-27T14:21:28 Z happy_node Two Currencies (JOI23_currencies) C++17
100 / 100
 4543 ms 57416 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=1e5+5, MK=18;

int N,M,Q;

vector<int> qry[MX];

ll S[MX], T[MX], X[MX], Y[MX], ans[MX], lca[MX];

int L[MX], R[MX], U[MX], V[MX];

int up[MX][MK], tin[MX], tout[MX], timer=0;

struct segtree {
        ll t[4*MX], lazy[4*MX];

        void push(int v, int l, int r) {
        	t[v]+=lazy[v];
        	if(l!=r) {
        		lazy[2*v+0]+=lazy[v];
        		lazy[2*v+1]+=lazy[v];
        	}
        	lazy[v]=0;
        }
 
        void update(int v, int l, int r, int ql, int qr, int val) {
        	push(v,l,r);
                if(qr<l || r<ql) return;
                if(ql<=l && qr>=r) {
                        lazy[v]+=val;
                        push(v,l,r);
                        return;
                }
                int mid = (l + r) >> 1;
                update(v*2+0, l, mid+0, ql, qr, val);
                update(v*2+1, mid+1, r, ql, qr, val);
                t[v] = t[v*2+0] + t[v*2+1];
        }
 
        ll query(int v, int l, int r, int ql, int qr) {
        	push(v,l,r);
                if(ql > r || qr < l) return 0;
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return query(v*2+0, l, mid+0, ql, qr) + query(v*2+1, mid+1, r, ql, qr);
        }

        void upd(int pos, ll val) {
        	update(1,1,N,tin[pos],tout[pos],val);
        }

        ll que(int a, int b) {
        	return query(1,1,N,tin[a],tin[a])-query(1,1,N,tin[b],tin[b]);
        }

        void reset() {
        	for(int i=0;i<4*MX;i++) t[i]=0,lazy[i]=0;
        }
} st, tt;

vector<int> adj[MX];
 
void dfs(int v, int p) {
        tin[v]=++timer;
        up[v][0]=p;
        for(int k = 1; k < MK; k++) {
                up[v][k]=up[up[v][k-1]][k-1];
        }
        for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u,v);
        }
        tout[v]=timer;
}
 
bool isAnc(int v, int anc) { 
        if(tin[anc]<=tin[v] && tout[v]<=tout[anc]) return 1;
        return 0;
}

int LCA(int u, int v) {
        if(isAnc(u, v)) return v;
        if(isAnc(v, u)) return u;
        for(int k=MK-1; k>=0;k--) {
                if(!isAnc(u, up[v][k]) && up[v][k]!=0) v = up[v][k];
        }
        return up[v][0];
}

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

	cin>>N>>M>>Q;

	for(int i=1;i<=N-1;i++) {
		int u,v;
		cin>>u>>v;

		adj[u].push_back(v);
		adj[v].push_back(u);
		U[i]=u;
		V[i]=v;
	}

	vector<pair<int,int>> e;
	e.push_back({0,0});

	for(int i=0;i<M;i++) {
		int p,c;
		cin>>p>>c;
		e.push_back({c,p});
	}

	dfs(1,0);

	sort(e.begin(),e.end());

	for(int i=0;i<Q;i++) {
		cin>>S[i]>>T[i]>>X[i]>>Y[i];
		L[i]=0,R[i]=M;
		int m=(L[i]+R[i])/2;
		lca[i]=LCA(S[i],T[i]);
		qry[m].push_back(i);
	}

	for(int i=1;i<=N-1;i++) {
		if(isAnc(V[i],U[i])) swap(U[i],V[i]); // V parentnya 
	}

	for(int ii=0;ii<20;ii++) {
		st.reset();
		tt.reset();
		// activate

		for(int i=1;i<=M;i++) {
			auto [c,p]=e[i];
			st.upd(U[p],1);
		}

		vector<pair<int,int>> nxt;

		for(int i=0;i<=M;i++) {
			auto [c,p]=e[i];
			if(i>0) {
				st.upd(U[p],-1);
				tt.upd(U[p],c);
			}

			for(auto id:qry[i]) {
				ll s=tt.que(S[id],lca[id])+tt.que(T[id],lca[id]);

				if(s<=Y[id]) {
					ans[id]=st.que(S[id],lca[id])+st.que(T[id],lca[id]);
					L[id]=i+1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				} else {
					R[id]=i-1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				}
			}
		}

		for(int i=0;i<=M;i++) qry[i].clear();
		for(auto [i,id]:nxt) qry[i].push_back(id);
	}
	
	for(int i=0;i<Q;i++) {
		if(ans[i]>X[i]) {
			cout<<-1<<'\n';
		} else {
			cout<<X[i]-ans[i]<<'\n';
		}
	}

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 10 ms 25948 KB Output is correct
3 Correct 10 ms 25948 KB Output is correct
4 Correct 9 ms 26200 KB Output is correct
5 Correct 36 ms 26204 KB Output is correct
6 Correct 41 ms 26204 KB Output is correct
7 Correct 36 ms 26228 KB Output is correct
8 Correct 43 ms 26428 KB Output is correct
9 Correct 42 ms 26380 KB Output is correct
10 Correct 44 ms 26308 KB Output is correct
11 Correct 46 ms 26436 KB Output is correct
12 Correct 45 ms 26456 KB Output is correct
13 Correct 43 ms 26460 KB Output is correct
14 Correct 46 ms 26452 KB Output is correct
15 Correct 53 ms 26416 KB Output is correct
16 Correct 52 ms 26452 KB Output is correct
17 Correct 49 ms 26448 KB Output is correct
18 Correct 51 ms 26644 KB Output is correct
19 Correct 41 ms 26452 KB Output is correct
20 Correct 43 ms 26404 KB Output is correct
21 Correct 47 ms 26416 KB Output is correct
22 Correct 42 ms 26416 KB Output is correct
23 Correct 38 ms 26392 KB Output is correct
24 Correct 40 ms 26252 KB Output is correct
25 Correct 39 ms 26408 KB Output is correct
26 Correct 38 ms 26204 KB Output is correct
27 Correct 42 ms 26204 KB Output is correct
28 Correct 40 ms 26200 KB Output is correct
29 Correct 43 ms 26392 KB Output is correct
30 Correct 42 ms 26204 KB Output is correct
31 Correct 42 ms 26448 KB Output is correct
32 Correct 42 ms 26204 KB Output is correct
33 Correct 43 ms 26456 KB Output is correct
34 Correct 43 ms 26452 KB Output is correct
35 Correct 44 ms 26532 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25944 KB Output is correct
2 Correct 56 ms 26480 KB Output is correct
3 Correct 51 ms 26448 KB Output is correct
4 Correct 43 ms 26200 KB Output is correct
5 Correct 2546 ms 47420 KB Output is correct
6 Correct 2716 ms 51004 KB Output is correct
7 Correct 2735 ms 49964 KB Output is correct
8 Correct 2376 ms 46192 KB Output is correct
9 Correct 2321 ms 45888 KB Output is correct
10 Correct 3600 ms 52304 KB Output is correct
11 Correct 3505 ms 52400 KB Output is correct
12 Correct 3265 ms 52500 KB Output is correct
13 Correct 3442 ms 52392 KB Output is correct
14 Correct 3450 ms 52396 KB Output is correct
15 Correct 4272 ms 56960 KB Output is correct
16 Correct 4543 ms 57140 KB Output is correct
17 Correct 3706 ms 56952 KB Output is correct
18 Correct 3927 ms 52700 KB Output is correct
19 Correct 3731 ms 52548 KB Output is correct
20 Correct 4003 ms 52604 KB Output is correct
21 Correct 3396 ms 52464 KB Output is correct
22 Correct 3334 ms 52648 KB Output is correct
23 Correct 3194 ms 52712 KB Output is correct
24 Correct 3207 ms 52612 KB Output is correct
25 Correct 2974 ms 52648 KB Output is correct
26 Correct 2861 ms 52324 KB Output is correct
27 Correct 2904 ms 52196 KB Output is correct
28 Correct 2755 ms 52860 KB Output is correct
29 Correct 2633 ms 52636 KB Output is correct
30 Correct 2671 ms 51496 KB Output is correct
31 Correct 2617 ms 51124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26196 KB Output is correct
2 Correct 52 ms 26504 KB Output is correct
3 Correct 45 ms 26472 KB Output is correct
4 Correct 43 ms 26348 KB Output is correct
5 Correct 2340 ms 51508 KB Output is correct
6 Correct 2254 ms 51068 KB Output is correct
7 Correct 3012 ms 51288 KB Output is correct
8 Correct 3777 ms 57328 KB Output is correct
9 Correct 3558 ms 57268 KB Output is correct
10 Correct 3727 ms 57348 KB Output is correct
11 Correct 3130 ms 57308 KB Output is correct
12 Correct 3249 ms 57228 KB Output is correct
13 Correct 3113 ms 57408 KB Output is correct
14 Correct 2740 ms 57096 KB Output is correct
15 Correct 2648 ms 56732 KB Output is correct
16 Correct 2819 ms 57416 KB Output is correct
17 Correct 2942 ms 57172 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 10 ms 25948 KB Output is correct
3 Correct 10 ms 25948 KB Output is correct
4 Correct 9 ms 26200 KB Output is correct
5 Correct 36 ms 26204 KB Output is correct
6 Correct 41 ms 26204 KB Output is correct
7 Correct 36 ms 26228 KB Output is correct
8 Correct 43 ms 26428 KB Output is correct
9 Correct 42 ms 26380 KB Output is correct
10 Correct 44 ms 26308 KB Output is correct
11 Correct 46 ms 26436 KB Output is correct
12 Correct 45 ms 26456 KB Output is correct
13 Correct 43 ms 26460 KB Output is correct
14 Correct 46 ms 26452 KB Output is correct
15 Correct 53 ms 26416 KB Output is correct
16 Correct 52 ms 26452 KB Output is correct
17 Correct 49 ms 26448 KB Output is correct
18 Correct 51 ms 26644 KB Output is correct
19 Correct 41 ms 26452 KB Output is correct
20 Correct 43 ms 26404 KB Output is correct
21 Correct 47 ms 26416 KB Output is correct
22 Correct 42 ms 26416 KB Output is correct
23 Correct 38 ms 26392 KB Output is correct
24 Correct 40 ms 26252 KB Output is correct
25 Correct 39 ms 26408 KB Output is correct
26 Correct 38 ms 26204 KB Output is correct
27 Correct 42 ms 26204 KB Output is correct
28 Correct 40 ms 26200 KB Output is correct
29 Correct 43 ms 26392 KB Output is correct
30 Correct 42 ms 26204 KB Output is correct
31 Correct 42 ms 26448 KB Output is correct
32 Correct 42 ms 26204 KB Output is correct
33 Correct 43 ms 26456 KB Output is correct
34 Correct 43 ms 26452 KB Output is correct
35 Correct 44 ms 26532 KB Output is correct
36 Correct 10 ms 25944 KB Output is correct
37 Correct 56 ms 26480 KB Output is correct
38 Correct 51 ms 26448 KB Output is correct
39 Correct 43 ms 26200 KB Output is correct
40 Correct 2546 ms 47420 KB Output is correct
41 Correct 2716 ms 51004 KB Output is correct
42 Correct 2735 ms 49964 KB Output is correct
43 Correct 2376 ms 46192 KB Output is correct
44 Correct 2321 ms 45888 KB Output is correct
45 Correct 3600 ms 52304 KB Output is correct
46 Correct 3505 ms 52400 KB Output is correct
47 Correct 3265 ms 52500 KB Output is correct
48 Correct 3442 ms 52392 KB Output is correct
49 Correct 3450 ms 52396 KB Output is correct
50 Correct 4272 ms 56960 KB Output is correct
51 Correct 4543 ms 57140 KB Output is correct
52 Correct 3706 ms 56952 KB Output is correct
53 Correct 3927 ms 52700 KB Output is correct
54 Correct 3731 ms 52548 KB Output is correct
55 Correct 4003 ms 52604 KB Output is correct
56 Correct 3396 ms 52464 KB Output is correct
57 Correct 3334 ms 52648 KB Output is correct
58 Correct 3194 ms 52712 KB Output is correct
59 Correct 3207 ms 52612 KB Output is correct
60 Correct 2974 ms 52648 KB Output is correct
61 Correct 2861 ms 52324 KB Output is correct
62 Correct 2904 ms 52196 KB Output is correct
63 Correct 2755 ms 52860 KB Output is correct
64 Correct 2633 ms 52636 KB Output is correct
65 Correct 2671 ms 51496 KB Output is correct
66 Correct 2617 ms 51124 KB Output is correct
67 Correct 13 ms 26196 KB Output is correct
68 Correct 52 ms 26504 KB Output is correct
69 Correct 45 ms 26472 KB Output is correct
70 Correct 43 ms 26348 KB Output is correct
71 Correct 2340 ms 51508 KB Output is correct
72 Correct 2254 ms 51068 KB Output is correct
73 Correct 3012 ms 51288 KB Output is correct
74 Correct 3777 ms 57328 KB Output is correct
75 Correct 3558 ms 57268 KB Output is correct
76 Correct 3727 ms 57348 KB Output is correct
77 Correct 3130 ms 57308 KB Output is correct
78 Correct 3249 ms 57228 KB Output is correct
79 Correct 3113 ms 57408 KB Output is correct
80 Correct 2740 ms 57096 KB Output is correct
81 Correct 2648 ms 56732 KB Output is correct
82 Correct 2819 ms 57416 KB Output is correct
83 Correct 2942 ms 57172 KB Output is correct
84 Correct 2832 ms 46868 KB Output is correct
85 Correct 2549 ms 46724 KB Output is correct
86 Correct 2191 ms 45924 KB Output is correct
87 Correct 3365 ms 51892 KB Output is correct
88 Correct 3824 ms 52236 KB Output is correct
89 Correct 3579 ms 52308 KB Output is correct
90 Correct 3608 ms 52316 KB Output is correct
91 Correct 3740 ms 52636 KB Output is correct
92 Correct 3900 ms 55536 KB Output is correct
93 Correct 3927 ms 56788 KB Output is correct
94 Correct 4331 ms 52432 KB Output is correct
95 Correct 4204 ms 52400 KB Output is correct
96 Correct 4170 ms 52476 KB Output is correct
97 Correct 4143 ms 52648 KB Output is correct
98 Correct 3991 ms 52452 KB Output is correct
99 Correct 3723 ms 52260 KB Output is correct
100 Correct 3693 ms 52692 KB Output is correct
101 Correct 3689 ms 52708 KB Output is correct
102 Correct 3206 ms 53084 KB Output is correct
103 Correct 3021 ms 53140 KB Output is correct
104 Correct 2958 ms 52964 KB Output is correct
105 Correct 2824 ms 50808 KB Output is correct
106 Correct 2829 ms 53120 KB Output is correct
107 Correct 2829 ms 50360 KB Output is correct
108 Correct 3019 ms 51012 KB Output is correct