oj.uz

답안 #956973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956973 2024-04-02T18:16:52 Z Nonoze Two Currencies (JOI23_currencies) C++17
58 / 100
 1058 ms 140908 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, nb;
vector<vector<int>> up;
int base=0;

void dfs(int s, int prec=-1) {
	for (auto u: adj[s]) {
		if (u.fi==prec) continue;
		nb[u.fi]=nb[s]+(u.se?1:0);
		if (u.se) base=u.se;
		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);
	}
}

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];
}

void subtask2() {
	depth.resize(n), nb.resize(n), up.resize(n, vector<int>(20));
	dfs(0);
	while (q--) {
		int s, t, a, b; cin >> s >> t >> a >> b;
		int lca=get_lca(--s, --t);
		int sumnb=nb[s]+nb[t]-2*nb[lca];
		int take=b/base;
		int res=-1;
		take=sumnb-take;
		if (take<=0) {
			cout << a << endl;
			continue;
		}
		cmax(res, a-take);
		cout << res << endl;
	}
}


vector<int> vaut, contains, sqr, nbelements;
int tot=0, squarevaut;
int ask(int s, int t, 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 subtask3() {
	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]++});
		}
	}


	vector<int> ordre(1, 0);
	vector<pair<int, int>> nxt(n, {-1, -1});
	vector<int> empl(n, 0);
	int lst=-1;
	for (int i=0; i<n; i++) {
		for (auto u: adj[ordre.back()]) {
			if (u.fi!=lst) {
				nxt[ordre.back()]={u.fi, u.se};
				lst=ordre.back();
				ordre.push_back(u.fi);
				empl[ordre.back()]=sz(ordre)-1;
				break;
			}
		}
	}


	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;
		if (--s>--t) swap(s, t);
		queries.push_back({{s, t, a, b}, i});
	}
	int square=sqrt(n);
	sort(all(queries), [&](auto &a, auto &b){
		if ((int)(empl[a.fi[0]]/square)!=(int)(empl[b.fi[0]]/square)) return (int)(empl[a.fi[0]]/square)<(int)(empl[b.fi[0]]/square);
		return a.fi[1]<b.fi[1];
	});
	int left=empl[queries[0].fi[0]], right=left;
	for (int i=0; i<q; i++) {
		int s=queries[i].fi[0], t=queries[i].fi[1];
		while (right<empl[t]) {
			sqr[nxt[ordre[right]].se/squarevaut]+=vaut[nxt[ordre[right]].se];
			contains[nxt[ordre[right]].se]++;
			nbelements[nxt[ordre[right]].se/squarevaut]++;
			tot++;
			right++;
		}
		while (left>empl[s]) {
			left--;
			sqr[nxt[ordre[left]].se/squarevaut]+=vaut[nxt[ordre[left]].se];
			contains[nxt[ordre[left]].se]++;
			nbelements[nxt[ordre[left]].se/squarevaut]++;
			tot++;
		}
		while (left<empl[s]) {
			sqr[nxt[ordre[left]].se/squarevaut]-=vaut[nxt[ordre[left]].se];
			contains[nxt[ordre[left]].se]--;
			nbelements[nxt[ordre[left]].se/squarevaut]--;
			tot--;
			left++;
		}
		while (right>empl[t]) {
			right--;
			sqr[nxt[ordre[right]].se/squarevaut]-=vaut[nxt[ordre[right]].se];
			contains[nxt[ordre[right]].se]--;
			nbelements[nxt[ordre[right]].se/squarevaut]--;
			tot--;
		}
		answers[queries[i].se]=ask(s, t, queries[i].fi[2], queries[i].fi[3]);
	}
	for (auto u: answers) cout << u << endl;
}


void solve() {
	cin >> n >> m >> q;
	adj.resize(n);
	bool sub3=true;
	vector<pair<int, int>> edges;
	for (int i=1; i<n; i++) {
		int u, v; cin >> u >> v;
		edges.push_back({--u, --v});
		if (v!=u+1) sub3=false;
		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++;
		}
	}
	if (sub3) return subtask3();
	return subtask2();
}

Subtask #1
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 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 2908 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 4 ms 2908 KB Output is correct
5 Correct 291 ms 125676 KB Output is correct
6 Correct 253 ms 90708 KB Output is correct
7 Correct 261 ms 102108 KB Output is correct
8 Correct 232 ms 105104 KB Output is correct
9 Correct 237 ms 104712 KB Output is correct
10 Correct 344 ms 128872 KB Output is correct
11 Correct 332 ms 127848 KB Output is correct
12 Correct 321 ms 128600 KB Output is correct
13 Correct 339 ms 128448 KB Output is correct
14 Correct 326 ms 129132 KB Output is correct
15 Correct 435 ms 135304 KB Output is correct
16 Correct 449 ms 136552 KB Output is correct
17 Correct 427 ms 134764 KB Output is correct
18 Correct 421 ms 128460 KB Output is correct
19 Correct 393 ms 128260 KB Output is correct
20 Correct 405 ms 127768 KB Output is correct
21 Correct 320 ms 128172 KB Output is correct
22 Correct 330 ms 126644 KB Output is correct
23 Correct 322 ms 126568 KB Output is correct
24 Correct 330 ms 127300 KB Output is correct
25 Correct 287 ms 140908 KB Output is correct
26 Correct 294 ms 140508 KB Output is correct
27 Correct 284 ms 139376 KB Output is correct
28 Correct 294 ms 127420 KB Output is correct
29 Correct 273 ms 128108 KB Output is correct
30 Correct 288 ms 129356 KB Output is correct
31 Correct 301 ms 127464 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 6 ms 2664 KB Output is correct
3 Correct 7 ms 2652 KB Output is correct
4 Correct 7 ms 2776 KB Output is correct
5 Correct 751 ms 106180 KB Output is correct
6 Correct 686 ms 105780 KB Output is correct
7 Correct 740 ms 81124 KB Output is correct
8 Correct 1039 ms 121784 KB Output is correct
9 Correct 1046 ms 121960 KB Output is correct
10 Correct 1058 ms 121196 KB Output is correct
11 Correct 608 ms 126544 KB Output is correct
12 Correct 684 ms 126320 KB Output is correct
13 Correct 691 ms 126372 KB Output is correct
14 Correct 313 ms 121032 KB Output is correct
15 Correct 325 ms 122540 KB Output is correct
16 Correct 882 ms 120908 KB Output is correct
17 Correct 919 ms 122220 KB Output is correct

Subtask #4
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 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -