oj.uz

Submission #957448

# Submission time Handle Problem Language Result Execution time Memory
957448 2024-04-03T17:49:34 Z Nonoze Two Currencies (JOI23_currencies) C++17
100 / 100
 2434 ms 200540 KB 
/*
*	Author: Nonoze
*	Created: Sunday 31/03/2024
*/
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long


#ifdef _IN_LOCAL
	#include <bits/DebugTemplate.h>
#else
	#define dbg(...) ;
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) cout << x << endl, return;
const int MOD = 1e9+7;
const ll inf = 1e18;


template<typename T> constexpr bool cmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> constexpr bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }


void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, m, q;
vector<set<pair<int, int>>> adj;
vector<int> depth, in, out, id;
vector<vector<int>> nxt;
vector<vector<int>> up;
int curr=0, toadd=-1;

void dfs(int s, int prec=-1) {
	id.push_back(s), in[s]=curr++;
	nxt.push_back({});
	for (auto u: adj[s]) {
		if (u.fi==prec) continue;
		if (id.back()==s) nxt[curr-1].push_back(u.se);
		if (toadd!=-1) nxt[toadd].push_back(u.se), toadd=-1;
		depth[u.fi]=depth[s]+1;
		up[u.fi][0]=s;
		for (int i=1; i<20; i++) {
			up[u.fi][i]=up[ up[u.fi][i-1] ][i-1];
		}
		dfs(u.fi, s);
		nxt[curr-1].push_back(-u.se);
		toadd=curr-1;
	}
	if (sz(adj)<=2) toadd=-1;
	id.push_back(s), out[s]=curr++;
	nxt.push_back({});
}

int get_lca(int a, int b) {
	if (depth[a]<depth[b]) swap(a, b);
	int k=depth[a]-depth[b];
	for (int i=0; i<20; i++) {
		if (k&(1<<i)) {
			a=up[a][i];
		}
	}
	if (a==b) return a;
	for (int i=19; i>=0; i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}


vector<int> vaut, contains, sqr, nbelements;
int tot=0, squarevaut;
int ask(int a, int b) {
	int comp=0, empl=0;
	for (; empl<sz(sqr) && sqr[empl]<=b; empl++) {
		b-=sqr[empl];
		comp+=nbelements[empl];
	}
	for (empl*=squarevaut; empl<sz(contains) && vaut[empl]*contains[empl]<=b; empl++) {
		b-=contains[empl]*vaut[empl];
		comp+=contains[empl];
	}

	return max(-1LL, a-tot+comp);
}


void resolve() {

	map<int, int> mp;
	for (int i=0; i<n; i++) {
		for (auto u: adj[i]) {
			if (u.fi<i) continue;
			mp[u.se]++;
		}
	}
	mp[0]++;
	int compteur=0;
	for (auto &u: mp) {
		int sz=u.se;
		u.se=compteur; compteur+=sz;
	}
	squarevaut=sqrt(compteur);
	vaut.resize(compteur, 0), contains.resize(compteur, 0), sqr.resize(squarevaut+5, 0), nbelements.resize(squarevaut+5, 0);
	for (int i=0; i<n; i++) {
		auto temp=adj[i];
		for (auto &u: temp) {
			if (u.fi<i) continue;
			vaut[mp[u.se]]=u.se;
			adj[i].erase({u.fi, u.se});
			adj[i].insert({u.fi, mp[u.se]});
			adj[u.fi].erase({i, u.se});
			adj[u.fi].insert({i, mp[u.se]++});
		}
	}


	depth.resize(n), in.resize(n), out.resize(n), up.resize(n, vector<int>(20));
	dfs(0);

	vector<int> answers(q);
	vector<pair<vector<int>, int>> queries;
	for (int i=0; i<q; i++) {
		int s, t, a, b; cin >> s >> t >> a >> b;
		s--, t--;
		if (in[s]>in[t]) swap(s, t);
		int l, r, lca=get_lca(s, t);
		if (lca==s) l=in[s], r=in[t];
		else l=out[s], r=in[t];
		queries.push_back({{l, r, a, b}, i});
	}
	int square=sqrt(2*n);
	sort(all(queries), [&](auto &a, auto &b){
		if (a.fi[0]/square!=b.fi[0]/square) return a.fi[0]/square<b.fi[0]/square;
		return a.fi[1]<b.fi[1];
	});
	int left=0, right=0;
	for (int i=0; i<q; i++) {
		int l=queries[i].fi[0], r=queries[i].fi[1];
		while (right<r) {
			for (auto u: nxt[right]) {
				if (!u) continue;
				int empl=abs(u), sign=(contains[empl]?-1:1);
				sqr[empl/squarevaut]+=vaut[empl]*sign;
				contains[empl]+=sign;
				nbelements[empl/squarevaut]+=sign;
				tot+=sign;
			}
			right++;
		}
		while (left>l) {
			left--;
			for (auto u: nxt[left]) {
				if (!u) continue;
				int empl=abs(u), sign=(contains[empl]?-1:1);
				sqr[empl/squarevaut]+=vaut[empl]*sign;
				contains[empl]+=sign;
				nbelements[empl/squarevaut]+=sign;
				tot+=sign;
			}
		}
		while (left<l) {
			for (auto u: nxt[left]) {
				if (!u) continue;
				int empl=abs(u), sign=(contains[empl]?-1:1);
				sqr[empl/squarevaut]+=vaut[empl]*sign;
				contains[empl]+=sign;
				nbelements[empl/squarevaut]+=sign;
				tot+=sign;
			}
			left++;
		}
		while (right>r) {
			right--;
			for (auto u: nxt[right]) {
				if (!u) continue;
				int empl=abs(u), sign=(contains[empl]?-1:1);
				sqr[empl/squarevaut]+=vaut[empl]*sign;
				contains[empl]+=sign;
				nbelements[empl/squarevaut]+=sign;
				tot+=sign;
			}
		}
		answers[queries[i].se]=ask(queries[i].fi[2], queries[i].fi[3]);
	}
	for (auto u: answers) cout << u << endl;
}


void solve() {
	cin >> n >> m >> q;
	adj.resize(n);
	vector<pair<int, int>> edges;
	for (int i=1; i<n; i++) {
		int u, v; cin >> u >> v;
		edges.push_back({--u, --v});
		adj[u].insert({v, 0});
		adj[v].insert({u, 0});
	}
	vector<stack<int>> updates(n-1);
	for (int i=0; i<m; i++) {
		int p, c; cin >> p >> c;
		updates[--p].push(c);
	}
	for (int i=0; i<sz(updates); i++) {
		if (updates[i].empty()) continue;
		auto act=updates[i];
		int u=edges[i].fi, v=edges[i].se;
		adj[u].erase({v, 0}); adj[v].erase({u, 0});
		adj[u].insert({v, act.top()});
		adj[v].insert({u, act.top()});
		int weightbase=act.top(); act.pop();
		while (!act.empty()) {
			int weight=act.top(); act.pop();
			adj[u].erase({v, weightbase}); adj[v].erase({u, weightbase});
			adj[u].insert({n, weight});
			adj.push_back({});
			adj[n].insert({u, weight});
			adj[v].insert({n, weightbase});
			adj[n].insert({v, weightbase});
			u=n;
			n++;
		}
	}
	resolve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 11 ms 3420 KB Output is correct
6 Correct 10 ms 3420 KB Output is correct
7 Correct 7 ms 2608 KB Output is correct
8 Correct 12 ms 3672 KB Output is correct
9 Correct 10 ms 3420 KB Output is correct
10 Correct 11 ms 3684 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 11 ms 3420 KB Output is correct
13 Correct 8 ms 4020 KB Output is correct
14 Correct 8 ms 3932 KB Output is correct
15 Correct 9 ms 3676 KB Output is correct
16 Correct 10 ms 3676 KB Output is correct
17 Correct 9 ms 3616 KB Output is correct
18 Correct 10 ms 3676 KB Output is correct
19 Correct 11 ms 3416 KB Output is correct
20 Correct 10 ms 3420 KB Output is correct
21 Correct 10 ms 3672 KB Output is correct
22 Correct 10 ms 3540 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3932 KB Output is correct
25 Correct 8 ms 3932 KB Output is correct
26 Correct 6 ms 3676 KB Output is correct
27 Correct 6 ms 3672 KB Output is correct
28 Correct 9 ms 3676 KB Output is correct
29 Correct 8 ms 3672 KB Output is correct
30 Correct 10 ms 3420 KB Output is correct
31 Correct 10 ms 3544 KB Output is correct
32 Correct 10 ms 3416 KB Output is correct
33 Correct 7 ms 3932 KB Output is correct
34 Correct 7 ms 3932 KB Output is correct
35 Correct 7 ms 3932 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 3420 KB Output is correct
3 Correct 10 ms 3416 KB Output is correct
4 Correct 12 ms 3748 KB Output is correct
5 Correct 1992 ms 148560 KB Output is correct
6 Correct 1494 ms 112880 KB Output is correct
7 Correct 1550 ms 125908 KB Output is correct
8 Correct 1479 ms 127776 KB Output is correct
9 Correct 1495 ms 125900 KB Output is correct
10 Correct 2263 ms 158556 KB Output is correct
11 Correct 2276 ms 160132 KB Output is correct
12 Correct 2268 ms 159172 KB Output is correct
13 Correct 2260 ms 160404 KB Output is correct
14 Correct 2314 ms 157512 KB Output is correct
15 Correct 1233 ms 176520 KB Output is correct
16 Correct 1253 ms 175100 KB Output is correct
17 Correct 1241 ms 175356 KB Output is correct
18 Correct 2269 ms 159968 KB Output is correct
19 Correct 2358 ms 161968 KB Output is correct
20 Correct 2258 ms 158264 KB Output is correct
21 Correct 2237 ms 158612 KB Output is correct
22 Correct 2301 ms 155980 KB Output is correct
23 Correct 2249 ms 157152 KB Output is correct
24 Correct 2274 ms 157452 KB Output is correct
25 Correct 1012 ms 178992 KB Output is correct
26 Correct 620 ms 180572 KB Output is correct
27 Correct 1144 ms 176004 KB Output is correct
28 Correct 447 ms 155664 KB Output is correct
29 Correct 428 ms 159560 KB Output is correct
30 Correct 1877 ms 156844 KB Output is correct
31 Correct 1893 ms 159496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 3928 KB Output is correct
3 Correct 8 ms 3932 KB Output is correct
4 Correct 9 ms 4056 KB Output is correct
5 Correct 746 ms 156240 KB Output is correct
6 Correct 681 ms 151048 KB Output is correct
7 Correct 800 ms 124976 KB Output is correct
8 Correct 1095 ms 184740 KB Output is correct
9 Correct 1096 ms 182644 KB Output is correct
10 Correct 1123 ms 185348 KB Output is correct
11 Correct 752 ms 198464 KB Output is correct
12 Correct 774 ms 197480 KB Output is correct
13 Correct 739 ms 200540 KB Output is correct
14 Correct 383 ms 183484 KB Output is correct
15 Correct 378 ms 186268 KB Output is correct
16 Correct 808 ms 183508 KB Output is correct
17 Correct 792 ms 183292 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 11 ms 3420 KB Output is correct
6 Correct 10 ms 3420 KB Output is correct
7 Correct 7 ms 2608 KB Output is correct
8 Correct 12 ms 3672 KB Output is correct
9 Correct 10 ms 3420 KB Output is correct
10 Correct 11 ms 3684 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 11 ms 3420 KB Output is correct
13 Correct 8 ms 4020 KB Output is correct
14 Correct 8 ms 3932 KB Output is correct
15 Correct 9 ms 3676 KB Output is correct
16 Correct 10 ms 3676 KB Output is correct
17 Correct 9 ms 3616 KB Output is correct
18 Correct 10 ms 3676 KB Output is correct
19 Correct 11 ms 3416 KB Output is correct
20 Correct 10 ms 3420 KB Output is correct
21 Correct 10 ms 3672 KB Output is correct
22 Correct 10 ms 3540 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3932 KB Output is correct
25 Correct 8 ms 3932 KB Output is correct
26 Correct 6 ms 3676 KB Output is correct
27 Correct 6 ms 3672 KB Output is correct
28 Correct 9 ms 3676 KB Output is correct
29 Correct 8 ms 3672 KB Output is correct
30 Correct 10 ms 3420 KB Output is correct
31 Correct 10 ms 3544 KB Output is correct
32 Correct 10 ms 3416 KB Output is correct
33 Correct 7 ms 3932 KB Output is correct
34 Correct 7 ms 3932 KB Output is correct
35 Correct 7 ms 3932 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 10 ms 3420 KB Output is correct
38 Correct 10 ms 3416 KB Output is correct
39 Correct 12 ms 3748 KB Output is correct
40 Correct 1992 ms 148560 KB Output is correct
41 Correct 1494 ms 112880 KB Output is correct
42 Correct 1550 ms 125908 KB Output is correct
43 Correct 1479 ms 127776 KB Output is correct
44 Correct 1495 ms 125900 KB Output is correct
45 Correct 2263 ms 158556 KB Output is correct
46 Correct 2276 ms 160132 KB Output is correct
47 Correct 2268 ms 159172 KB Output is correct
48 Correct 2260 ms 160404 KB Output is correct
49 Correct 2314 ms 157512 KB Output is correct
50 Correct 1233 ms 176520 KB Output is correct
51 Correct 1253 ms 175100 KB Output is correct
52 Correct 1241 ms 175356 KB Output is correct
53 Correct 2269 ms 159968 KB Output is correct
54 Correct 2358 ms 161968 KB Output is correct
55 Correct 2258 ms 158264 KB Output is correct
56 Correct 2237 ms 158612 KB Output is correct
57 Correct 2301 ms 155980 KB Output is correct
58 Correct 2249 ms 157152 KB Output is correct
59 Correct 2274 ms 157452 KB Output is correct
60 Correct 1012 ms 178992 KB Output is correct
61 Correct 620 ms 180572 KB Output is correct
62 Correct 1144 ms 176004 KB Output is correct
63 Correct 447 ms 155664 KB Output is correct
64 Correct 428 ms 159560 KB Output is correct
65 Correct 1877 ms 156844 KB Output is correct
66 Correct 1893 ms 159496 KB Output is correct
67 Correct 1 ms 344 KB Output is correct
68 Correct 7 ms 3928 KB Output is correct
69 Correct 8 ms 3932 KB Output is correct
70 Correct 9 ms 4056 KB Output is correct
71 Correct 746 ms 156240 KB Output is correct
72 Correct 681 ms 151048 KB Output is correct
73 Correct 800 ms 124976 KB Output is correct
74 Correct 1095 ms 184740 KB Output is correct
75 Correct 1096 ms 182644 KB Output is correct
76 Correct 1123 ms 185348 KB Output is correct
77 Correct 752 ms 198464 KB Output is correct
78 Correct 774 ms 197480 KB Output is correct
79 Correct 739 ms 200540 KB Output is correct
80 Correct 383 ms 183484 KB Output is correct
81 Correct 378 ms 186268 KB Output is correct
82 Correct 808 ms 183508 KB Output is correct
83 Correct 792 ms 183292 KB Output is correct
84 Correct 1881 ms 137356 KB Output is correct
85 Correct 1435 ms 106312 KB Output is correct
86 Correct 1035 ms 93476 KB Output is correct
87 Correct 2406 ms 163632 KB Output is correct
88 Correct 2385 ms 163424 KB Output is correct
89 Correct 2358 ms 165996 KB Output is correct
90 Correct 2382 ms 164448 KB Output is correct
91 Correct 2369 ms 166024 KB Output is correct
92 Correct 1349 ms 175284 KB Output is correct
93 Correct 1412 ms 182508 KB Output is correct
94 Correct 2406 ms 168124 KB Output is correct
95 Correct 2417 ms 166392 KB Output is correct
96 Correct 2405 ms 168732 KB Output is correct
97 Correct 2434 ms 165548 KB Output is correct
98 Correct 2327 ms 165508 KB Output is correct
99 Correct 2366 ms 162512 KB Output is correct
100 Correct 2366 ms 163636 KB Output is correct
101 Correct 2332 ms 166332 KB Output is correct
102 Correct 876 ms 186228 KB Output is correct
103 Correct 1090 ms 184668 KB Output is correct
104 Correct 967 ms 185744 KB Output is correct
105 Correct 580 ms 164412 KB Output is correct
106 Correct 548 ms 164276 KB Output is correct
107 Correct 2011 ms 165672 KB Output is correct
108 Correct 2011 ms 162384 KB Output is correct