oj.uz

답안 #832614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832614 2023-08-21T12:38:33 Z beaconmc Two Currencies (JOI23_currencies) C++14
28 / 100
 563 ms 40876 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

vector<ll> edges[100001];
ll toll[100001];
ll par[100001];
ll depth[100001];
ll pref[100001];
ll ancc[100001][20];

ll fixcost = 0;

vector<vector<ll>> stuff;


void dfs(ll a, ll p, ll d){
	par[a] = p;
	depth[a] = d;
	for (auto&i : edges[a]){
		if (i!=p) dfs(i, a, d+1);
	}
}

void dfs2(ll a, ll p){
	if (p!=-1) pref[a] = pref[p] + toll[a];
	for (auto&i : edges[a]){
		if (i!=p) dfs2(i, a);
	}
}
ll anc(ll a, ll jump){
	if (ancc[a][jump] != -1) return ancc[a][jump];
	if (depth[a] - (1<<jump) <= 0) return 1;
	if (jump == 0) return par[a];

	ancc[a][jump] = anc(anc(a, jump-1), jump-1);
	return ancc[a][jump];
}

ll lca(ll a, ll b){
	if (depth[a] < depth[b]) swap(a,b);
	FORNEG(i,19,-1) if (depth[anc(a, i)] >= depth[b]) a=anc(a,i);
	if (a==b) return a;
	FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b, i);

	return par[a];
}

int main(){
	FOR(i,0,100001) toll[i] = 0, par[i] = -1, depth[i] = 0, pref[i] = 0;
	FOR(i,0,100001) FOR(j,0,20) ancc[i][j] = -1;

	ll n,m,q;
	cin >> n >> m >> q;
	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		stuff.push_back({a,b});
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	dfs(1, -1, 0);

	FOR(i,0,m){
		ll c,d;

		cin >> c >> d;
		ll a = stuff[c-1][0];
		ll b = stuff[c-1][1];

		if (par[b] == a) toll[b] += d;
		else toll[a] += d;

		fixcost = d;
	}

	dfs2(1, -1);

	FOR(i,0,q){
		ll a,b,c,d;
		cin >> a >> b >> c >> d;

		ll total = 0;
		total += pref[a];
		total += pref[b];
		total -= 2*pref[lca(a,b)];
		ll count = total/fixcost;

		count -= (d/fixcost);
		count = max(count, (ll) 0);
		if (c-count < 0 ) cout << -1 << "\n";
		else cout << c-count << "\n";

	}



}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 21332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 21332 KB Output is correct
2 Correct 14 ms 21716 KB Output is correct
3 Correct 16 ms 21708 KB Output is correct
4 Correct 15 ms 21652 KB Output is correct
5 Correct 310 ms 35224 KB Output is correct
6 Correct 337 ms 32876 KB Output is correct
7 Correct 410 ms 34040 KB Output is correct
8 Correct 279 ms 33620 KB Output is correct
9 Correct 276 ms 33512 KB Output is correct
10 Correct 368 ms 35972 KB Output is correct
11 Correct 377 ms 36128 KB Output is correct
12 Correct 371 ms 36000 KB Output is correct
13 Correct 386 ms 36004 KB Output is correct
14 Correct 404 ms 36004 KB Output is correct
15 Correct 547 ms 40560 KB Output is correct
16 Correct 563 ms 40876 KB Output is correct
17 Correct 501 ms 40284 KB Output is correct
18 Correct 452 ms 35976 KB Output is correct
19 Correct 488 ms 35976 KB Output is correct
20 Correct 444 ms 36080 KB Output is correct
21 Correct 329 ms 35560 KB Output is correct
22 Correct 348 ms 35748 KB Output is correct
23 Correct 334 ms 35672 KB Output is correct
24 Correct 351 ms 35696 KB Output is correct
25 Correct 412 ms 36472 KB Output is correct
26 Correct 405 ms 36444 KB Output is correct
27 Correct 371 ms 36552 KB Output is correct
28 Correct 376 ms 35908 KB Output is correct
29 Correct 339 ms 35960 KB Output is correct
30 Correct 354 ms 36080 KB Output is correct
31 Correct 368 ms 36184 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 21332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 21332 KB Output isn't correct
2 Halted 0 ms 0 KB -