oj.uz

답안 #957446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957446 2024-04-03T17:47:01 Z Nonoze Two Currencies (JOI23_currencies) C++17
100 / 100
 2504 ms 201212 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];
	});
	// if (n>=50) return;
	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

# 결과 실행 시간 메모리 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 344 KB Output is correct
5 Correct 9 ms 3160 KB Output is correct
6 Correct 11 ms 3420 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 11 ms 3672 KB Output is correct
9 Correct 11 ms 3668 KB Output is correct
10 Correct 11 ms 3676 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 10 ms 3420 KB Output is correct
13 Correct 8 ms 3932 KB Output is correct
14 Correct 8 ms 3856 KB Output is correct
15 Correct 9 ms 3676 KB Output is correct
16 Correct 9 ms 3676 KB Output is correct
17 Correct 10 ms 3676 KB Output is correct
18 Correct 10 ms 3608 KB Output is correct
19 Correct 11 ms 3420 KB Output is correct
20 Correct 12 ms 3420 KB Output is correct
21 Correct 11 ms 3676 KB Output is correct
22 Correct 11 ms 3420 KB Output is correct
23 Correct 10 ms 3928 KB Output is correct
24 Correct 7 ms 3928 KB Output is correct
25 Correct 8 ms 3932 KB Output is correct
26 Correct 6 ms 3420 KB Output is correct
27 Correct 6 ms 3676 KB Output is correct
28 Correct 9 ms 3556 KB Output is correct
29 Correct 8 ms 3928 KB Output is correct
30 Correct 10 ms 3420 KB Output is correct
31 Correct 10 ms 3420 KB Output is correct
32 Correct 10 ms 3420 KB Output is correct
33 Correct 7 ms 3932 KB Output is correct
34 Correct 7 ms 3932 KB Output is correct
35 Correct 10 ms 3932 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 3416 KB Output is correct
3 Correct 12 ms 3420 KB Output is correct
4 Correct 11 ms 3564 KB Output is correct
5 Correct 1980 ms 147308 KB Output is correct
6 Correct 1493 ms 112964 KB Output is correct
7 Correct 1500 ms 124936 KB Output is correct
8 Correct 1530 ms 128176 KB Output is correct
9 Correct 1566 ms 125816 KB Output is correct
10 Correct 2343 ms 158432 KB Output is correct
11 Correct 2275 ms 158376 KB Output is correct
12 Correct 2280 ms 156252 KB Output is correct
13 Correct 2254 ms 156024 KB Output is correct
14 Correct 2315 ms 160012 KB Output is correct
15 Correct 1239 ms 177988 KB Output is correct
16 Correct 1255 ms 178568 KB Output is correct
17 Correct 1291 ms 175744 KB Output is correct
18 Correct 2274 ms 161220 KB Output is correct
19 Correct 2340 ms 163408 KB Output is correct
20 Correct 2350 ms 160416 KB Output is correct
21 Correct 2259 ms 157100 KB Output is correct
22 Correct 2236 ms 157916 KB Output is correct
23 Correct 2244 ms 155264 KB Output is correct
24 Correct 2273 ms 157720 KB Output is correct
25 Correct 1053 ms 177912 KB Output is correct
26 Correct 629 ms 177672 KB Output is correct
27 Correct 1132 ms 180060 KB Output is correct
28 Correct 495 ms 159584 KB Output is correct
29 Correct 439 ms 160672 KB Output is correct
30 Correct 1871 ms 159084 KB Output is correct
31 Correct 1884 ms 160256 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 7 ms 3960 KB Output is correct
3 Correct 7 ms 3932 KB Output is correct
4 Correct 7 ms 3928 KB Output is correct
5 Correct 788 ms 155368 KB Output is correct
6 Correct 714 ms 149684 KB Output is correct
7 Correct 806 ms 126528 KB Output is correct
8 Correct 1096 ms 181348 KB Output is correct
9 Correct 1102 ms 184424 KB Output is correct
10 Correct 1087 ms 184812 KB Output is correct
11 Correct 764 ms 201212 KB Output is correct
12 Correct 740 ms 198924 KB Output is correct
13 Correct 738 ms 199012 KB Output is correct
14 Correct 402 ms 184456 KB Output is correct
15 Correct 463 ms 187172 KB Output is correct
16 Correct 794 ms 187236 KB Output is correct
17 Correct 818 ms 187748 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 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 344 KB Output is correct
5 Correct 9 ms 3160 KB Output is correct
6 Correct 11 ms 3420 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 11 ms 3672 KB Output is correct
9 Correct 11 ms 3668 KB Output is correct
10 Correct 11 ms 3676 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 10 ms 3420 KB Output is correct
13 Correct 8 ms 3932 KB Output is correct
14 Correct 8 ms 3856 KB Output is correct
15 Correct 9 ms 3676 KB Output is correct
16 Correct 9 ms 3676 KB Output is correct
17 Correct 10 ms 3676 KB Output is correct
18 Correct 10 ms 3608 KB Output is correct
19 Correct 11 ms 3420 KB Output is correct
20 Correct 12 ms 3420 KB Output is correct
21 Correct 11 ms 3676 KB Output is correct
22 Correct 11 ms 3420 KB Output is correct
23 Correct 10 ms 3928 KB Output is correct
24 Correct 7 ms 3928 KB Output is correct
25 Correct 8 ms 3932 KB Output is correct
26 Correct 6 ms 3420 KB Output is correct
27 Correct 6 ms 3676 KB Output is correct
28 Correct 9 ms 3556 KB Output is correct
29 Correct 8 ms 3928 KB Output is correct
30 Correct 10 ms 3420 KB Output is correct
31 Correct 10 ms 3420 KB Output is correct
32 Correct 10 ms 3420 KB Output is correct
33 Correct 7 ms 3932 KB Output is correct
34 Correct 7 ms 3932 KB Output is correct
35 Correct 10 ms 3932 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 10 ms 3416 KB Output is correct
38 Correct 12 ms 3420 KB Output is correct
39 Correct 11 ms 3564 KB Output is correct
40 Correct 1980 ms 147308 KB Output is correct
41 Correct 1493 ms 112964 KB Output is correct
42 Correct 1500 ms 124936 KB Output is correct
43 Correct 1530 ms 128176 KB Output is correct
44 Correct 1566 ms 125816 KB Output is correct
45 Correct 2343 ms 158432 KB Output is correct
46 Correct 2275 ms 158376 KB Output is correct
47 Correct 2280 ms 156252 KB Output is correct
48 Correct 2254 ms 156024 KB Output is correct
49 Correct 2315 ms 160012 KB Output is correct
50 Correct 1239 ms 177988 KB Output is correct
51 Correct 1255 ms 178568 KB Output is correct
52 Correct 1291 ms 175744 KB Output is correct
53 Correct 2274 ms 161220 KB Output is correct
54 Correct 2340 ms 163408 KB Output is correct
55 Correct 2350 ms 160416 KB Output is correct
56 Correct 2259 ms 157100 KB Output is correct
57 Correct 2236 ms 157916 KB Output is correct
58 Correct 2244 ms 155264 KB Output is correct
59 Correct 2273 ms 157720 KB Output is correct
60 Correct 1053 ms 177912 KB Output is correct
61 Correct 629 ms 177672 KB Output is correct
62 Correct 1132 ms 180060 KB Output is correct
63 Correct 495 ms 159584 KB Output is correct
64 Correct 439 ms 160672 KB Output is correct
65 Correct 1871 ms 159084 KB Output is correct
66 Correct 1884 ms 160256 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 7 ms 3960 KB Output is correct
69 Correct 7 ms 3932 KB Output is correct
70 Correct 7 ms 3928 KB Output is correct
71 Correct 788 ms 155368 KB Output is correct
72 Correct 714 ms 149684 KB Output is correct
73 Correct 806 ms 126528 KB Output is correct
74 Correct 1096 ms 181348 KB Output is correct
75 Correct 1102 ms 184424 KB Output is correct
76 Correct 1087 ms 184812 KB Output is correct
77 Correct 764 ms 201212 KB Output is correct
78 Correct 740 ms 198924 KB Output is correct
79 Correct 738 ms 199012 KB Output is correct
80 Correct 402 ms 184456 KB Output is correct
81 Correct 463 ms 187172 KB Output is correct
82 Correct 794 ms 187236 KB Output is correct
83 Correct 818 ms 187748 KB Output is correct
84 Correct 1872 ms 137452 KB Output is correct
85 Correct 1411 ms 108244 KB Output is correct
86 Correct 1045 ms 93188 KB Output is correct
87 Correct 2399 ms 164960 KB Output is correct
88 Correct 2359 ms 164172 KB Output is correct
89 Correct 2396 ms 165768 KB Output is correct
90 Correct 2368 ms 165360 KB Output is correct
91 Correct 2382 ms 166560 KB Output is correct
92 Correct 1388 ms 176736 KB Output is correct
93 Correct 1328 ms 179632 KB Output is correct
94 Correct 2381 ms 168328 KB Output is correct
95 Correct 2400 ms 167108 KB Output is correct
96 Correct 2398 ms 165832 KB Output is correct
97 Correct 2385 ms 168460 KB Output is correct
98 Correct 2386 ms 164292 KB Output is correct
99 Correct 2400 ms 163052 KB Output is correct
100 Correct 2399 ms 166304 KB Output is correct
101 Correct 2504 ms 163852 KB Output is correct
102 Correct 808 ms 181756 KB Output is correct
103 Correct 1100 ms 183392 KB Output is correct
104 Correct 1076 ms 184420 KB Output is correct
105 Correct 674 ms 166736 KB Output is correct
106 Correct 573 ms 162300 KB Output is correct
107 Correct 2158 ms 165912 KB Output is correct
108 Correct 2058 ms 166576 KB Output is correct