oj.uz

Submission #888711

# Submission time Handle Problem Language Result Execution time Memory
888711 2023-12-18T06:05:05 Z vjudge1 Two Currencies (JOI23_currencies) C++17
10 / 100
 806 ms 52412 KB 
#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 100005;
vi g[N];
map<pii, vi> mp;
int t;
int pre[N];
int n, q, timer;
int tin[N], tout[N];
int up[20][N];
int num[N];
void dfs(int v, int pr, int cnt){
	num[v] = cnt;
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 17; i++) {
        up[i][v] = up[i - 1][ up[i - 1][v] ];
    }
    for (int to : g[v]) {
        if (to == pr) continue;
        pre[to] = v;
        dfs(to, v, cnt+mp[{to, v}].size());
    }
    tout[v] = timer;
}

bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 17; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	vii cui;
	int cc = 0;
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
		cui.pb({a, b});
	}
	for(int i = 0; i < m; i++){
		int j, c;
		cin >> j >> c;j--;
		mp[cui[j]].pb(c);
		mp[{cui[j].ss, cui[j].ff}].pb(c);
		cc = c;
	}
	if(n > 2000){
		dfs(1, -1, 0);
		while(q--){
			int a, b, x, y;
			cin >> a >> b >> x >> y;
			int cnt = num[a] + num[b] - (2 * num[lca(a, b)]);
			cnt = max(0ll, cnt - (y/cc));
			y -= (y/cc)*cc;
			x -= cnt;
			cout << (x < 0 ? -1 : x) << '\n';
		}
	}else{
		vi pas;
		while(q--){
			int s, x, y;
			cin >> s >> t >> x >> y;
			dfs(s, -1, 0);
			int r = t;
			while(r!=s){
				for(auto i:mp[{r, pre[r]}])pas.pb(i);
				r = pre[r];
			}
			sort(all(pas));
			for(auto i:pas){
				if(i <= y)y -= i;
				else x--;
			}pas.clear();
			cout << (x<0?-1:x) << '\n';
		}
	}
	
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

currencies.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 2 ms 19288 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Correct 306 ms 20104 KB Output is correct
6 Correct 538 ms 19876 KB Output is correct
7 Correct 281 ms 19712 KB Output is correct
8 Correct 577 ms 19804 KB Output is correct
9 Correct 594 ms 20156 KB Output is correct
10 Correct 575 ms 20136 KB Output is correct
11 Correct 569 ms 19880 KB Output is correct
12 Correct 588 ms 20136 KB Output is correct
13 Correct 806 ms 20176 KB Output is correct
14 Correct 801 ms 20308 KB Output is correct
15 Correct 708 ms 20052 KB Output is correct
16 Correct 732 ms 20236 KB Output is correct
17 Correct 680 ms 19968 KB Output is correct
18 Correct 695 ms 20016 KB Output is correct
19 Correct 462 ms 20076 KB Output is correct
20 Correct 460 ms 19888 KB Output is correct
21 Correct 455 ms 19904 KB Output is correct
22 Correct 470 ms 20052 KB Output is correct
23 Correct 584 ms 19876 KB Output is correct
24 Correct 608 ms 20088 KB Output is correct
25 Correct 599 ms 20304 KB Output is correct
26 Correct 572 ms 19868 KB Output is correct
27 Correct 569 ms 19864 KB Output is correct
28 Correct 573 ms 19864 KB Output is correct
29 Correct 586 ms 19880 KB Output is correct
30 Correct 585 ms 19888 KB Output is correct
31 Correct 573 ms 19912 KB Output is correct
32 Correct 573 ms 20052 KB Output is correct
33 Correct 425 ms 20060 KB Output is correct
34 Correct 447 ms 20172 KB Output is correct
35 Correct 437 ms 20424 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 585 ms 19904 KB Output is correct
3 Correct 579 ms 19804 KB Output is correct
4 Correct 599 ms 19904 KB Output is correct
5 Incorrect 236 ms 43452 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19292 KB Output is correct
2 Correct 429 ms 20176 KB Output is correct
3 Correct 430 ms 20172 KB Output is correct
4 Correct 431 ms 20056 KB Output is correct
5 Incorrect 129 ms 52412 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 2 ms 19288 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Correct 306 ms 20104 KB Output is correct
6 Correct 538 ms 19876 KB Output is correct
7 Correct 281 ms 19712 KB Output is correct
8 Correct 577 ms 19804 KB Output is correct
9 Correct 594 ms 20156 KB Output is correct
10 Correct 575 ms 20136 KB Output is correct
11 Correct 569 ms 19880 KB Output is correct
12 Correct 588 ms 20136 KB Output is correct
13 Correct 806 ms 20176 KB Output is correct
14 Correct 801 ms 20308 KB Output is correct
15 Correct 708 ms 20052 KB Output is correct
16 Correct 732 ms 20236 KB Output is correct
17 Correct 680 ms 19968 KB Output is correct
18 Correct 695 ms 20016 KB Output is correct
19 Correct 462 ms 20076 KB Output is correct
20 Correct 460 ms 19888 KB Output is correct
21 Correct 455 ms 19904 KB Output is correct
22 Correct 470 ms 20052 KB Output is correct
23 Correct 584 ms 19876 KB Output is correct
24 Correct 608 ms 20088 KB Output is correct
25 Correct 599 ms 20304 KB Output is correct
26 Correct 572 ms 19868 KB Output is correct
27 Correct 569 ms 19864 KB Output is correct
28 Correct 573 ms 19864 KB Output is correct
29 Correct 586 ms 19880 KB Output is correct
30 Correct 585 ms 19888 KB Output is correct
31 Correct 573 ms 19912 KB Output is correct
32 Correct 573 ms 20052 KB Output is correct
33 Correct 425 ms 20060 KB Output is correct
34 Correct 447 ms 20172 KB Output is correct
35 Correct 437 ms 20424 KB Output is correct
36 Correct 3 ms 19288 KB Output is correct
37 Correct 585 ms 19904 KB Output is correct
38 Correct 579 ms 19804 KB Output is correct
39 Correct 599 ms 19904 KB Output is correct
40 Incorrect 236 ms 43452 KB Output isn't correct
41 Halted 0 ms 0 KB -