oj.uz

답안 #854510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854510 2023-09-27T19:17:55 Z serifefedartar Two Currencies (JOI23_currencies) C++17
0 / 100
 3 ms 10588 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll MAXN = 1e5 + 5;

struct Query {
	int from, to, bs_l, bs_r;
	ll gold, silver;
	int low;
	Query(int a, int b, ll x, ll y, ll c, ll d) : from(a), to(b), bs_l(x), bs_r(y), gold(c), silver(d) { }
};

vector<vector<int>> graph;
vector<pair<int,int>> edges;
vector<pair<ll,int>> cost;
vector<Query> queries;
int depth[MAXN], up[LOGN][MAXN], cnt[MAXN], counter[MAXN];
int tin[MAXN], tout[MAXN], mx_silver[MAXN], ans[MAXN];
ll fen[MAXN], fen2[MAXN];
int T = 0;

void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;

		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u, node);
	}
	tout[node] = T;
}

void dfs2(int node, int parent) {
	counter[node] = counter[parent] + cnt[node];
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs2(u, node);
	}
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN-1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

void update(int k, ll val) {
	while (k < MAXN) {
		fen[k] += val;
		if (val > 0)
			fen2[k]++;
		else
			fen2[k]--;
		k += k & -k;
	}
}

void range(int l, int r, ll val) {
	update(l, val);
	update(r+1, -val);
}

ll get(int k) {
	k = tin[k];
	ll res = 0; 
	while (k) {
		res += fen[k];
		k -= k & -k;
	}
	return res;
}

int get2(int k) {
	k = tin[k];
	int res = 0;
	while (k) {
		res += fen2[k];
		k -= k & -k;
	}
	return res;
}

void parallel(ll l, ll r, vector<int> qs) {
	if (l > r || qs.size() == 0)
		return ;
	if (l == r) {
		int node = cost[l-1].s;
		ll C = cost[l-1].f;
		range(tin[node], tout[node], C);
		for (auto u : qs) {
			Query qry = queries[u];
			ll total_silver = get(qry.from) + get(qry.to) - 2 * get(qry.low);
			if (total_silver <= qry.silver)
				ans[u] = get2(qry.from) + get2(qry.to) - 2 * get2(qry.low);
		}
		range(tin[node], tout[node], -C);
		return ; 
	}


	int mid = l + (r-l)/2;
	for (ll i = l; i <= mid; i++) {
		int node = cost[i-1].s;
		ll C = cost[i-1].f;
		range(tin[node], tout[node], C);
	}

	vector<int> left, right;
	for (auto u : qs) {
		Query qry = queries[u];
		ll total_silver = get(qry.from) + get(qry.to) - 2 * get(qry.low);
		if (total_silver <= qry.silver) {
			right.push_back(u);
			ans[u] = get2(qry.from) + get2(qry.to) - 2 * get2(qry.low);
		} else
			left.push_back(u);
	}

	parallel(mid+1, r, right);
	for (int i = mid; i >= l; i--) {
		int node = cost[i-1].s;
		ll C = cost[i-1].f;
		range(tin[node], tout[node], -C);
	}
	parallel(l, mid, left);
}

int main() {
	fast
	int N, M, Q, u, v;
	cin >> N >> M >> Q;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> u >> v;
		edges.push_back({u, v});
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs(1, 1);

	for (int i = 0; i < M; i++) {
		ll P, C;
		cin >> P >> C;
		int edge = (depth[edges[P-1].f] > depth[edges[P-1].s] ? edges[P-1].f : edges[P-1].s);
		cnt[edge]++;
		cost.push_back({C, edge});
	}
	sort(cost.begin(), cost.end());
	dfs2(1, 1);

	for (int i = 0; i < Q; i++) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		queries.push_back(Query(a, b, 1, cost.size(), c, d));
		queries.back().low = lca(queries.back().from, queries.back().to);
	}

	vector<int> qs;
	for (int i = 0; i < Q; i++)
		qs.push_back(i);

	parallel(1, cost.size(), qs);

	for (int i = 0; i < Q; i++) {
		int all = counter[queries[i].from] + counter[queries[i].to] - 2 * counter[lca(queries[i].from, queries[i].to)];
		int can_be_silver = ans[i];
		if (all-can_be_silver > queries[i].gold)
			cout << "-1\n";
		else
			cout << all - can_be_silver << "\n";
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 28.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 32.0

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