#include <bits/stdc++.h>
#define nosg "Two Currencies"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define maxn 6000005
#define gb(i, j) ((i >> j) & 1)
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r) (rng);
}
int n, m, q;
pii edge[maxn], tram[maxn];
vector<int> o[maxn];
int cnt;
int in[maxn], out[maxn];
int h[maxn], cha[maxn][20];
void dfs(int u, int par)
{
in[u] = ++ cnt;
for(int v : o[u])
{
if(v == par) continue;
h[v] = h[u] + 1;
cha[v][0] = u;
fi(j, 1, 17) cha[v][j] = cha[cha[v][j - 1]][j - 1];
dfs(v, u);
}
out[u] = cnt;
}
int lca(int u, int v)
{
if(h[u] < h[v]) swap(u, v);
int kc = h[u] - h[v];
fi(j, 0, 17) if(gb(kc, j)) u = cha[u][j];
if(u == v) return u;
fid(j, 17, 0)
{
if(cha[u][j] != cha[v][j])
{
u = cha[u][j];
v = cha[v][j];
}
}
return cha[u][0];
}
int nNode;
int ver[maxn], L[maxn], R[maxn];
ll st[maxn], lazy[maxn];
int newleaf(int id, int l, int r, ll val)
{
int p = ++ nNode;
L[p] = L[id], R[p] = R[id];
st[p] = st[id] + 1ll * (r - l + 1) * val;
lazy[p] = lazy[id] + val;
return p;
}
void down(int id, int l, int r)
{
if(lazy[id])
{
if(l != r)
{
int mid = (l + r) >> 1;
L[id] = newleaf(L[id], l, mid, lazy[id]);
R[id] = newleaf(R[id], mid + 1, r, lazy[id]);
}
}
lazy[id] = 0;
}
int newparent(int lef, int rig)
{
int p = ++ nNode;
L[p] = lef, R[p] = rig;
st[p] = st[L[p]] + st[R[p]];
return p;
}
int update(int oid, int u, int v, ll val, int l = 1, int r = n)
{
if(v < l || r < u) return oid;
if(u <= l && r <= v) return newleaf(oid, l, r, val);
down(oid, l, r);
int mid = (l + r) >> 1;
return newparent( update(L[oid], u, v, val, l, mid), update(R[oid], u, v, val, mid + 1, r) );
}
ll get(int id, int i, int l = 1, int r = n)
{
if(i < l || r < i) return 0;
if(l == r) return st[id];
down(id, l, r);
int mid = (l + r) >> 1;
return get(L[id], i, l, mid) + get(R[id], i, mid + 1, r);
}
int nNode2;
int ver2[maxn], L2[maxn], R2[maxn];
ll st2[maxn], lazy2[maxn];
int newleaf2(int id, int l, int r, ll val)
{
int p = ++ nNode2;
L2[p] = L2[id], R2[p] = R2[id];
st2[p] = st2[id] + 1ll * (r - l + 1) * val;
lazy2[p] = lazy2[id] + val;
return p;
}
void down2(int id, int l, int r)
{
if(lazy2[id])
{
if(l != r)
{
int mid = (l + r) >> 1;
L2[id] = newleaf2(L2[id], l, mid, lazy2[id]);
R2[id] = newleaf2(R2[id], mid + 1, r, lazy2[id]);
}
}
lazy2[id] = 0;
}
int newparent2(int lef, int rig)
{
int p = ++ nNode2;
L2[p] = lef, R2[p] = rig;
st2[p] = st2[L2[p]] + st2[R2[p]];
return p;
}
int update2(int oid, int u, int v, int l = 1, int r = n)
{
if(v < l || r < u) return oid;
if(u <= l && r <= v) return newleaf2(oid, l, r, 1);
down2(oid, l, r);
int mid = (l + r) >> 1;
return newparent2( update2(L2[oid], u, v, l, mid), update2(R2[oid], u, v, mid + 1, r) );
}
ll get2(int id, int i, int l = 1, int r = n)
{
if(i < l || r < i) return 0;
if(l == r) return st2[id];
down2(id, l, r);
int mid = (l + r) >> 1;
return get2(L2[id], i, l, mid) + get2(R2[id], i, mid + 1, r);
}
int main()
{
// freopen(nosg".inp","r",stdin);
// freopen(nosg".out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> q;
fi(i, 1, n - 1)
{
cin >> edge[i].f >> edge[i].s;
int u = edge[i].f, v = edge[i].s;
o[u].push_back(v);
o[v].push_back(u);
}
dfs(1, -1);
fi(i, 1, m) cin >> tram[i].f >> tram[i].s;
sort(tram + 1, tram + m + 1, [](pii x, pii y) {
return x.s < y.s;
});
fi(i, 1, m)
{
int j = tram[i].f, val = tram[i].s;
int u = edge[j].f, v = edge[j].s;
if(h[u] > h[v]) swap(u, v);
ver[i] = update(ver[i - 1], in[v], out[v], 1ll * val);
ver2[i] = update2(ver2[i - 1], in[v], out[v]);
}
fi(i, 1, q)
{
int u, v;
ll S, G;
cin >> u >> v >> G >> S;
if(h[u] > h[v]) swap(u, v);
int par = lca(u, v);
int l = 1, r = m;
while(l <= r)
{
int mid = (l + r) >> 1;
if(get(ver[mid], in[v]) + get(ver[mid], in[u]) - 2ll * get(ver[mid], in[par]) <= S) l = mid + 1;
else r = mid - 1;
}
int sum = get2(ver2[m], in[v]) + get2(ver2[m], in[u]) - 2ll * get2(ver2[m], in[par]);
int use = get2(ver2[r], in[v]) + get2(ver2[r], in[u]) - 2ll * get2(ver2[r], in[par]);
cout << (G - (sum - use) >= 0 ? G - (sum - use) : -1) << '\n';
}
/// ------------------check time!-----------------///
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
150156 KB |
Output is correct |
2 |
Correct |
43 ms |
152148 KB |
Output is correct |
3 |
Correct |
43 ms |
152156 KB |
Output is correct |
4 |
Correct |
48 ms |
152144 KB |
Output is correct |
5 |
Correct |
50 ms |
156644 KB |
Output is correct |
6 |
Correct |
56 ms |
156460 KB |
Output is correct |
7 |
Correct |
52 ms |
157996 KB |
Output is correct |
8 |
Correct |
56 ms |
158548 KB |
Output is correct |
9 |
Correct |
56 ms |
160852 KB |
Output is correct |
10 |
Correct |
54 ms |
158292 KB |
Output is correct |
11 |
Correct |
56 ms |
160712 KB |
Output is correct |
12 |
Correct |
57 ms |
160816 KB |
Output is correct |
13 |
Correct |
58 ms |
170068 KB |
Output is correct |
14 |
Correct |
60 ms |
167864 KB |
Output is correct |
15 |
Correct |
59 ms |
167848 KB |
Output is correct |
16 |
Correct |
60 ms |
164432 KB |
Output is correct |
17 |
Correct |
59 ms |
165200 KB |
Output is correct |
18 |
Correct |
59 ms |
165456 KB |
Output is correct |
19 |
Correct |
53 ms |
157780 KB |
Output is correct |
20 |
Correct |
52 ms |
155768 KB |
Output is correct |
21 |
Correct |
53 ms |
155648 KB |
Output is correct |
22 |
Correct |
52 ms |
155996 KB |
Output is correct |
23 |
Correct |
52 ms |
156496 KB |
Output is correct |
24 |
Correct |
52 ms |
155984 KB |
Output is correct |
25 |
Correct |
54 ms |
158036 KB |
Output is correct |
26 |
Correct |
53 ms |
155988 KB |
Output is correct |
27 |
Correct |
53 ms |
156024 KB |
Output is correct |
28 |
Correct |
52 ms |
156240 KB |
Output is correct |
29 |
Correct |
50 ms |
156288 KB |
Output is correct |
30 |
Correct |
54 ms |
156756 KB |
Output is correct |
31 |
Correct |
55 ms |
158544 KB |
Output is correct |
32 |
Correct |
53 ms |
156240 KB |
Output is correct |
33 |
Correct |
58 ms |
170064 KB |
Output is correct |
34 |
Correct |
59 ms |
168680 KB |
Output is correct |
35 |
Correct |
59 ms |
168656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
152352 KB |
Output is correct |
2 |
Correct |
54 ms |
156752 KB |
Output is correct |
3 |
Correct |
57 ms |
158544 KB |
Output is correct |
4 |
Correct |
56 ms |
156240 KB |
Output is correct |
5 |
Correct |
2207 ms |
307532 KB |
Output is correct |
6 |
Correct |
2969 ms |
309272 KB |
Output is correct |
7 |
Correct |
2652 ms |
274348 KB |
Output is correct |
8 |
Correct |
1880 ms |
266868 KB |
Output is correct |
9 |
Correct |
1878 ms |
286288 KB |
Output is correct |
10 |
Correct |
4062 ms |
355872 KB |
Output is correct |
11 |
Correct |
3621 ms |
346756 KB |
Output is correct |
12 |
Correct |
3464 ms |
351252 KB |
Output is correct |
13 |
Correct |
3781 ms |
363448 KB |
Output is correct |
14 |
Correct |
3660 ms |
346768 KB |
Output is correct |
15 |
Runtime error |
733 ms |
757396 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
152280 KB |
Output is correct |
2 |
Correct |
61 ms |
170064 KB |
Output is correct |
3 |
Correct |
66 ms |
168780 KB |
Output is correct |
4 |
Correct |
61 ms |
168784 KB |
Output is correct |
5 |
Runtime error |
692 ms |
636936 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
150156 KB |
Output is correct |
2 |
Correct |
43 ms |
152148 KB |
Output is correct |
3 |
Correct |
43 ms |
152156 KB |
Output is correct |
4 |
Correct |
48 ms |
152144 KB |
Output is correct |
5 |
Correct |
50 ms |
156644 KB |
Output is correct |
6 |
Correct |
56 ms |
156460 KB |
Output is correct |
7 |
Correct |
52 ms |
157996 KB |
Output is correct |
8 |
Correct |
56 ms |
158548 KB |
Output is correct |
9 |
Correct |
56 ms |
160852 KB |
Output is correct |
10 |
Correct |
54 ms |
158292 KB |
Output is correct |
11 |
Correct |
56 ms |
160712 KB |
Output is correct |
12 |
Correct |
57 ms |
160816 KB |
Output is correct |
13 |
Correct |
58 ms |
170068 KB |
Output is correct |
14 |
Correct |
60 ms |
167864 KB |
Output is correct |
15 |
Correct |
59 ms |
167848 KB |
Output is correct |
16 |
Correct |
60 ms |
164432 KB |
Output is correct |
17 |
Correct |
59 ms |
165200 KB |
Output is correct |
18 |
Correct |
59 ms |
165456 KB |
Output is correct |
19 |
Correct |
53 ms |
157780 KB |
Output is correct |
20 |
Correct |
52 ms |
155768 KB |
Output is correct |
21 |
Correct |
53 ms |
155648 KB |
Output is correct |
22 |
Correct |
52 ms |
155996 KB |
Output is correct |
23 |
Correct |
52 ms |
156496 KB |
Output is correct |
24 |
Correct |
52 ms |
155984 KB |
Output is correct |
25 |
Correct |
54 ms |
158036 KB |
Output is correct |
26 |
Correct |
53 ms |
155988 KB |
Output is correct |
27 |
Correct |
53 ms |
156024 KB |
Output is correct |
28 |
Correct |
52 ms |
156240 KB |
Output is correct |
29 |
Correct |
50 ms |
156288 KB |
Output is correct |
30 |
Correct |
54 ms |
156756 KB |
Output is correct |
31 |
Correct |
55 ms |
158544 KB |
Output is correct |
32 |
Correct |
53 ms |
156240 KB |
Output is correct |
33 |
Correct |
58 ms |
170064 KB |
Output is correct |
34 |
Correct |
59 ms |
168680 KB |
Output is correct |
35 |
Correct |
59 ms |
168656 KB |
Output is correct |
36 |
Correct |
46 ms |
152352 KB |
Output is correct |
37 |
Correct |
54 ms |
156752 KB |
Output is correct |
38 |
Correct |
57 ms |
158544 KB |
Output is correct |
39 |
Correct |
56 ms |
156240 KB |
Output is correct |
40 |
Correct |
2207 ms |
307532 KB |
Output is correct |
41 |
Correct |
2969 ms |
309272 KB |
Output is correct |
42 |
Correct |
2652 ms |
274348 KB |
Output is correct |
43 |
Correct |
1880 ms |
266868 KB |
Output is correct |
44 |
Correct |
1878 ms |
286288 KB |
Output is correct |
45 |
Correct |
4062 ms |
355872 KB |
Output is correct |
46 |
Correct |
3621 ms |
346756 KB |
Output is correct |
47 |
Correct |
3464 ms |
351252 KB |
Output is correct |
48 |
Correct |
3781 ms |
363448 KB |
Output is correct |
49 |
Correct |
3660 ms |
346768 KB |
Output is correct |
50 |
Runtime error |
733 ms |
757396 KB |
Execution killed with signal 11 |
51 |
Halted |
0 ms |
0 KB |
- |