#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e5 + 1;
int n, m, q;
vector<pii > ori_graph[1 + maxn];
int conv[1 + maxn];
vector<pii > graph[1 + maxn];
int road[1 + maxn];
int cost[1 + maxn];
vector<int> by_road[1 + maxn];
int node_cnt;
int from[1 + maxn];
int to[1 + maxn];
int gold[1 + maxn];
int silver[1 + maxn];
void virtual_dfs(int cur, int par) {
for(pii nei : ori_graph[cur]) {
if(nei.fi == par) {
continue;
}
if(by_road[nei.se].empty()) {
conv[nei.fi] = conv[cur];
virtual_dfs(nei.fi, cur);
} else {
int last = conv[cur];
for(int check_id : by_road[nei.se]) {
node_cnt++;
int nxt = node_cnt;
graph[last].pb(mp(nxt, check_id));
graph[nxt].pb(mp(last, check_id));
last = nxt;
}
conv[nei.fi] = last;
virtual_dfs(nei.fi, cur);
}
}
}
int visit_time;
int in[1 + maxn];
int out[1 + maxn];
int par_edge[1 + maxn];
int which[1 + 2 * maxn];
void dfs_euler(int cur, int par) {
visit_time++;
in[cur] = visit_time;
for(pii nei : graph[cur]) {
if(nei.fi == par) {
par_edge[cur] = nei.se;
} else {
dfs_euler(nei.fi, cur);
}
}
visit_time++;
out[cur] = visit_time;
}
const int block_size = 320;
const int blocks = 320;
int block(int pos) {
return (pos - 1) / block_size + 1;
}
struct query {
int l, r, idx;
bool except;
bool operator < (const query &other) const {
if(block(l) != block(other.l)) {
return block(l) < block(other.l);
}
return r < other.r;
}
};
int ans[1 + maxn];
bool counted_in[1 + maxn];
int block_sum[1 + maxn];
int single_sum[1 + 2 * maxn];
int block_cnt[1 + maxn];
int single_cnt[1 + 2 * maxn];
int ord[1 + maxn];
int ord_cost[1 + maxn];
int total_cnt;
void add(int cur) {
cur = par_edge[cur];
cur = ord[cur];
block_sum[block(cur)] += ord_cost[cur];
single_sum[cur] += ord_cost[cur];
block_cnt[block(cur)]++;
single_cnt[cur]++;
total_cnt++;
}
void rem(int cur) {
cur = par_edge[cur];
cur = ord[cur];
block_sum[block(cur)] -= ord_cost[cur];
single_sum[cur] -= ord_cost[cur];
block_cnt[block(cur)]--;
single_cnt[cur]--;
total_cnt--;
}
void toggle(int cur) {
cur = which[cur];
if(cur == 1) {
return;
}
if(!counted_in[cur]) {
add(cur);
counted_in[cur] = true;
} else {
rem(cur);
counted_in[cur] = false;
}
}
void solve_queries() {
vector<query> queries;
for(int i = 1; i <= q; i++) {
int a = from[i], b = to[i];
if(in[a] > in[b]) {
swap(a, b);
}
if(in[a] <= in[b] && out[b] <= out[a]) {
queries.pb(query {in[a], in[b], i, true});
} else {
queries.pb(query {out[a], in[b], i, false});
}
}
sort(queries.begin(), queries.end());
int l = 1, r = 0;
for(query cur : queries) {
if(from[cur.idx] == to[cur.idx]) {
ans[cur.idx] = gold[cur.idx];
continue;
}
while(l > cur.l) {
l--;
toggle(l);
}
while(r < cur.r) {
r++;
toggle(r);
}
while(l < cur.l) {
toggle(l);
l++;
}
while(r > cur.r) {
toggle(r);
r--;
}
if(cur.except) {
toggle(l);
}
int limit = silver[cur.idx];
/*if(cur.idx == 1) {
cout << from[cur.idx] << " " << to[cur.idx] << "\n";
cout << total_cnt << "\n";
for(int i = 1; i <= m; i++) {
cout << counted_in[i];
}
cout << "\n";
}*/
int cur_sum = 0, cur_cnt = 0;
int res = 0;
for(int i = 1; i <= blocks; i++) {
if(cur_sum + block_sum[i] <= limit) {
cur_sum += block_sum[i];
cur_cnt += block_cnt[i];
} else {
for(int j = block_size * (i - 1) + 1; j <= block_size * i; j++) {
if(cur_sum <= limit) {
// if(cur.idx == 1) cout << "! " << res << " " << cur_cnt << "\n";
res = max(res, cur_cnt);
} else {
break;
}
if(cur.idx == 1) {
// cout << j << " - " << single_sum[j] << " - " << single_cnt[j] << "\n";
// pedig kellene kiirnia valamit
}
cur_sum += single_sum[j];
cur_cnt += single_cnt[j];
}
}
}
if(cur_sum <= limit) {
// if(cur.idx == 1) cout << "! " << res << " " << cur_cnt << "\n";
res = max(res, cur_cnt);
}
res = total_cnt - res;
res = gold[cur.idx] - res;
if(res < 0) {
res = -1;
}
ans[cur.idx] = res;
if(cur.except) {
toggle(l);
}
}
}
void solve() {
cin >> n >> m >> q;
for(int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
ori_graph[a].pb(mp(b, i));
ori_graph[b].pb(mp(a, i));
}
for(int i = 1; i <= m; i++) {
cin >> road[i] >> cost[i];
by_road[road[i]].pb(i);
}
for(int i = 1; i <= q; i++) {
cin >> from[i] >> to[i] >> gold[i] >> silver[i];
}
conv[1] = 1;
node_cnt = 1;
virtual_dfs(1, -1);
/*for(int i = 1; i <= n; i++) {
cout << conv[i] << " ";
}
cout << "\n" << node_cnt << "\n";
for(int i = 1; i <= m + 1; i++) {
cout << i << ":\n";
for(pii j : graph[i]) {
cout << j.fi << " " << j.se << "; ";
}
cout << "\n";
}*/
n = m + 1;
for(int i = 1; i <= q; i++) {
from[i] = conv[from[i]];
to[i] = conv[to[i]];
}
dfs_euler(1, -1);
for(int i = 1; i <= n; i++) {
which[in[i]] = which[out[i]] = i;
}
vector<pii > cost_order;
for(int i = 1; i <= m; i++) {
cost_order.pb(mp(cost[i], i));
}
sort(cost_order.begin(), cost_order.end());
for(int i = 0; i < m; i++) {
ord[cost_order[i].se] = i + 1;
ord_cost[i + 1] = cost_order[i].fi;
}
/*for(int i = 1; i <= m; i++) {
cout << ord[i] << " " << ord_cost[i] << "\n";
}
cout << "\n";*/
solve_queries();
for(int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 2 |
Correct |
4 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
5 ms |
15452 KB |
Output is correct |
| 4 |
Correct |
4 ms |
15452 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
15780 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
15964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
16220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 2 |
Correct |
4 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
5 ms |
15452 KB |
Output is correct |
| 4 |
Correct |
4 ms |
15452 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
15780 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
