oj.uz

Submission #783344

# Submission time Handle Problem Language Result Execution time Memory
783344 2023-07-14T21:12:33 Z fuad27 Two Currencies (JOI23_currencies) C++17
100 / 100
 978 ms 36920 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
const int N=100'010,L=20;
vector<pair<int,int>> g[N];
int up[N][L];
int tin[N], tout[N],depth[N];
int tinn[N];
int tim=1;
void dfs(int at, int p) {
	up[at][0]=p;
	for(int i = 1;i<L;i++) {
		up[at][i]=up[up[at][i-1]][i-1];
	}
	for(auto to:g[at]) {
		if(to.first==p)continue;
		tinn[to.first]=tim;
		tin[to.second]=tim++;
		depth[to.first]=depth[at]+1;
		dfs(to.first,at);
		tout[to.second]=tim++;
	}
}
int lca(int a, int b) {
	if(depth[a]<depth[b])swap(a,b);
	int k=depth[a]-depth[b];
	for(int i = L-1;i>=0;i--) {
		if(k&(1<<i))a=up[a][i];
	}
	if(a==b)return a;
	for(int j = L-1;j>=0;j--) {
		if(up[a][j]!=up[b][j]) {
			a=up[a][j];
			b=up[b][j];
		}
	}
	return up[a][0];
}
template<typename T>
struct BIT {
  int N_;
  vector<T> F_;
  BIT(int n) {
    N_=n;
    F_=vector<T>(n+1);
  }
  void update(int at, T val) {
    for(;at<=N_;at+=at&-at)F_[at]+=val;
  }
  T query(int l, int r) {
    if(l!=1) {
      return query(1,r)-query(1,l);
    }
    T res=0;
    for(;r>0;r-=r&-r)res+=F_[r];
    return res;
  }
};
struct query {
	int u, v, lc;
	long long x,y;
};
signed main () {
	cin.tie(0)->sync_with_stdio(0);		
	for(int i = 0;i<N;i++)
		for(int j = 0;j<L;j++)
			up[i][j]=1;
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0;i<n-1;i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back({b,i});
		g[b].push_back({a,i});
	}
	vector<pair<long long, int>> v(m);
	for(int i = 0;i<m;i++) {
		cin >> v[i].second >> v[i].first;
		v[i].second--;
	}
	sort(v.begin(),v.end());
	tinn[1]=tim++;
	dfs(1,1);
	query c[q];
	for(int i=0;i<q;i++){
		cin >> c[i].u >> c[i].v >> c[i].x >> c[i].y;
		c[i].lc=lca(c[i].u,c[i].v);
	}
	int l[q], r[q],res[q];
	for(int i = 0;i<q;i++) {
		l[i]=0, r[i]=m;
		res[i]=-1;
	}
	BIT<long long> b3(2*n+10);
	for(int i = 0;i<m;i++) {
		b3.update(tin[v[i].second],1);	
		b3.update(tout[v[i].second],-1);
	}
	while(1) {
		vector<pair<int,int>> queries;
		for(int i = 0;i<q;i++) {
			if(l[i]>r[i])continue;
			int tm=(l[i]+r[i])/2;
			queries.push_back({tm,i});
		}
		if(queries.size()==0)break;
		sort(queries.begin(),queries.end());
		BIT<long long> b1(2*n+10),b2(2*n+10);
		int pt=0;
		for(int i = 0;i<queries.size();i++) {
			while(pt<queries[i].first) {
				b1.update(tin[v[pt].second],v[pt].first);
				b1.update(tout[v[pt].second],-v[pt].first);
				b2.update(tin[v[pt].second],1);
				b2.update(tout[v[pt].second],-1);
				pt++;
			}
			int j=queries[i].second;
			int dst=b3.query(tinn[c[j].lc], tinn[c[j].u])+b3.query(tinn[c[j].lc],tinn[c[j].v]);
			if(b1.query(tinn[c[j].lc],tinn[c[j].u])+b1.query(tinn[c[j].lc],tinn[c[j].v])<=c[j].y) {
				l[j]=queries[i].first+1;
				if(dst-(b2.query(tinn[c[j].lc],tinn[c[j].u])+b2.query(tinn[c[j].lc],tinn[c[j].v]))<=c[j].x) {
					res[j]=c[j].x-(dst-(b2.query(tinn[c[j].lc],tinn[c[j].u])+b2.query(tinn[c[j].lc],tinn[c[j].v])));
				}
			}
			else {
				r[j]=queries[i].first-1;
			}
		}
	}
	for(int i = 0;i<q;i++) {
		cout << res[i] << "\n";
	}
	return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i = 0;i<queries.size();i++) {
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 4 ms 10452 KB Output is correct
3 Correct 4 ms 10452 KB Output is correct
4 Correct 4 ms 10500 KB Output is correct
5 Correct 8 ms 10768 KB Output is correct
6 Correct 10 ms 10836 KB Output is correct
7 Correct 10 ms 10848 KB Output is correct
8 Correct 12 ms 10984 KB Output is correct
9 Correct 11 ms 10836 KB Output is correct
10 Correct 10 ms 10836 KB Output is correct
11 Correct 11 ms 10940 KB Output is correct
12 Correct 11 ms 10896 KB Output is correct
13 Correct 11 ms 10996 KB Output is correct
14 Correct 11 ms 10896 KB Output is correct
15 Correct 10 ms 10948 KB Output is correct
16 Correct 11 ms 10836 KB Output is correct
17 Correct 10 ms 10836 KB Output is correct
18 Correct 11 ms 10900 KB Output is correct
19 Correct 10 ms 10944 KB Output is correct
20 Correct 9 ms 10876 KB Output is correct
21 Correct 11 ms 10836 KB Output is correct
22 Correct 9 ms 10900 KB Output is correct
23 Correct 11 ms 10896 KB Output is correct
24 Correct 10 ms 10896 KB Output is correct
25 Correct 10 ms 10844 KB Output is correct
26 Correct 11 ms 10964 KB Output is correct
27 Correct 9 ms 10836 KB Output is correct
28 Correct 9 ms 10836 KB Output is correct
29 Correct 9 ms 10936 KB Output is correct
30 Correct 10 ms 10836 KB Output is correct
31 Correct 10 ms 10836 KB Output is correct
32 Correct 10 ms 10896 KB Output is correct
33 Correct 10 ms 10964 KB Output is correct
34 Correct 10 ms 10900 KB Output is correct
35 Correct 10 ms 10992 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10488 KB Output is correct
2 Correct 13 ms 10836 KB Output is correct
3 Correct 10 ms 10896 KB Output is correct
4 Correct 10 ms 10836 KB Output is correct
5 Correct 448 ms 29932 KB Output is correct
6 Correct 561 ms 29356 KB Output is correct
7 Correct 509 ms 30044 KB Output is correct
8 Correct 411 ms 28676 KB Output is correct
9 Correct 386 ms 27680 KB Output is correct
10 Correct 660 ms 33336 KB Output is correct
11 Correct 666 ms 33376 KB Output is correct
12 Correct 668 ms 33504 KB Output is correct
13 Correct 650 ms 33328 KB Output is correct
14 Correct 661 ms 33384 KB Output is correct
15 Correct 663 ms 36348 KB Output is correct
16 Correct 671 ms 36720 KB Output is correct
17 Correct 664 ms 35808 KB Output is correct
18 Correct 669 ms 33008 KB Output is correct
19 Correct 689 ms 33156 KB Output is correct
20 Correct 700 ms 33220 KB Output is correct
21 Correct 535 ms 33040 KB Output is correct
22 Correct 590 ms 33060 KB Output is correct
23 Correct 550 ms 33080 KB Output is correct
24 Correct 546 ms 33132 KB Output is correct
25 Correct 562 ms 33664 KB Output is correct
26 Correct 563 ms 33656 KB Output is correct
27 Correct 563 ms 33772 KB Output is correct
28 Correct 502 ms 33292 KB Output is correct
29 Correct 432 ms 33256 KB Output is correct
30 Correct 488 ms 33412 KB Output is correct
31 Correct 490 ms 33408 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 10 ms 10964 KB Output is correct
3 Correct 10 ms 10904 KB Output is correct
4 Correct 10 ms 11012 KB Output is correct
5 Correct 411 ms 33252 KB Output is correct
6 Correct 417 ms 32944 KB Output is correct
7 Correct 568 ms 27168 KB Output is correct
8 Correct 667 ms 36780 KB Output is correct
9 Correct 677 ms 36900 KB Output is correct
10 Correct 700 ms 36908 KB Output is correct
11 Correct 616 ms 36920 KB Output is correct
12 Correct 608 ms 36856 KB Output is correct
13 Correct 601 ms 36872 KB Output is correct
14 Correct 525 ms 36884 KB Output is correct
15 Correct 515 ms 36708 KB Output is correct
16 Correct 570 ms 36856 KB Output is correct
17 Correct 565 ms 36860 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 4 ms 10452 KB Output is correct
3 Correct 4 ms 10452 KB Output is correct
4 Correct 4 ms 10500 KB Output is correct
5 Correct 8 ms 10768 KB Output is correct
6 Correct 10 ms 10836 KB Output is correct
7 Correct 10 ms 10848 KB Output is correct
8 Correct 12 ms 10984 KB Output is correct
9 Correct 11 ms 10836 KB Output is correct
10 Correct 10 ms 10836 KB Output is correct
11 Correct 11 ms 10940 KB Output is correct
12 Correct 11 ms 10896 KB Output is correct
13 Correct 11 ms 10996 KB Output is correct
14 Correct 11 ms 10896 KB Output is correct
15 Correct 10 ms 10948 KB Output is correct
16 Correct 11 ms 10836 KB Output is correct
17 Correct 10 ms 10836 KB Output is correct
18 Correct 11 ms 10900 KB Output is correct
19 Correct 10 ms 10944 KB Output is correct
20 Correct 9 ms 10876 KB Output is correct
21 Correct 11 ms 10836 KB Output is correct
22 Correct 9 ms 10900 KB Output is correct
23 Correct 11 ms 10896 KB Output is correct
24 Correct 10 ms 10896 KB Output is correct
25 Correct 10 ms 10844 KB Output is correct
26 Correct 11 ms 10964 KB Output is correct
27 Correct 9 ms 10836 KB Output is correct
28 Correct 9 ms 10836 KB Output is correct
29 Correct 9 ms 10936 KB Output is correct
30 Correct 10 ms 10836 KB Output is correct
31 Correct 10 ms 10836 KB Output is correct
32 Correct 10 ms 10896 KB Output is correct
33 Correct 10 ms 10964 KB Output is correct
34 Correct 10 ms 10900 KB Output is correct
35 Correct 10 ms 10992 KB Output is correct
36 Correct 4 ms 10488 KB Output is correct
37 Correct 13 ms 10836 KB Output is correct
38 Correct 10 ms 10896 KB Output is correct
39 Correct 10 ms 10836 KB Output is correct
40 Correct 448 ms 29932 KB Output is correct
41 Correct 561 ms 29356 KB Output is correct
42 Correct 509 ms 30044 KB Output is correct
43 Correct 411 ms 28676 KB Output is correct
44 Correct 386 ms 27680 KB Output is correct
45 Correct 660 ms 33336 KB Output is correct
46 Correct 666 ms 33376 KB Output is correct
47 Correct 668 ms 33504 KB Output is correct
48 Correct 650 ms 33328 KB Output is correct
49 Correct 661 ms 33384 KB Output is correct
50 Correct 663 ms 36348 KB Output is correct
51 Correct 671 ms 36720 KB Output is correct
52 Correct 664 ms 35808 KB Output is correct
53 Correct 669 ms 33008 KB Output is correct
54 Correct 689 ms 33156 KB Output is correct
55 Correct 700 ms 33220 KB Output is correct
56 Correct 535 ms 33040 KB Output is correct
57 Correct 590 ms 33060 KB Output is correct
58 Correct 550 ms 33080 KB Output is correct
59 Correct 546 ms 33132 KB Output is correct
60 Correct 562 ms 33664 KB Output is correct
61 Correct 563 ms 33656 KB Output is correct
62 Correct 563 ms 33772 KB Output is correct
63 Correct 502 ms 33292 KB Output is correct
64 Correct 432 ms 33256 KB Output is correct
65 Correct 488 ms 33412 KB Output is correct
66 Correct 490 ms 33408 KB Output is correct
67 Correct 4 ms 10452 KB Output is correct
68 Correct 10 ms 10964 KB Output is correct
69 Correct 10 ms 10904 KB Output is correct
70 Correct 10 ms 11012 KB Output is correct
71 Correct 411 ms 33252 KB Output is correct
72 Correct 417 ms 32944 KB Output is correct
73 Correct 568 ms 27168 KB Output is correct
74 Correct 667 ms 36780 KB Output is correct
75 Correct 677 ms 36900 KB Output is correct
76 Correct 700 ms 36908 KB Output is correct
77 Correct 616 ms 36920 KB Output is correct
78 Correct 608 ms 36856 KB Output is correct
79 Correct 601 ms 36872 KB Output is correct
80 Correct 525 ms 36884 KB Output is correct
81 Correct 515 ms 36708 KB Output is correct
82 Correct 570 ms 36856 KB Output is correct
83 Correct 565 ms 36860 KB Output is correct
84 Correct 495 ms 28332 KB Output is correct
85 Correct 484 ms 25596 KB Output is correct
86 Correct 426 ms 24748 KB Output is correct
87 Correct 682 ms 33288 KB Output is correct
88 Correct 735 ms 33356 KB Output is correct
89 Correct 683 ms 33312 KB Output is correct
90 Correct 742 ms 33408 KB Output is correct
91 Correct 756 ms 33356 KB Output is correct
92 Correct 822 ms 33884 KB Output is correct
93 Correct 768 ms 35688 KB Output is correct
94 Correct 872 ms 33064 KB Output is correct
95 Correct 833 ms 33212 KB Output is correct
96 Correct 957 ms 33064 KB Output is correct
97 Correct 978 ms 33060 KB Output is correct
98 Correct 706 ms 33080 KB Output is correct
99 Correct 755 ms 32968 KB Output is correct
100 Correct 777 ms 33056 KB Output is correct
101 Correct 704 ms 33068 KB Output is correct
102 Correct 763 ms 33700 KB Output is correct
103 Correct 682 ms 33612 KB Output is correct
104 Correct 754 ms 33596 KB Output is correct
105 Correct 659 ms 33376 KB Output is correct
106 Correct 534 ms 33408 KB Output is correct
107 Correct 550 ms 33240 KB Output is correct
108 Correct 542 ms 33264 KB Output is correct