이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct query{
int a, b, lc, gold, silver, need, l, r, i;
};
struct check{
int a, c;
};
int n, m, q;
const int N = 1e5 + 69;
vector <int> adj[N], work[N];
int seg[4 * N], lazy[4 * N], dep[N], lift[N][20], tin[N], tout[N], timer = 0;
query Q[N];
check C[N];
void dfs(int u, int par){
tin[u] = ++timer;
for (int v : adj[u]){
if (v == par) continue;
lift[v][0] = u;
dep[v] = dep[u] + 1;
dfs(v, u);
}
tout[u] = timer;
}
int findlca(int a, int b){
if (dep[a] < dep[b]) swap(a, b);
int del = dep[a] - dep[b];
for (int i = 0; i < 20; i++) if (del >> i & 1) a = lift[a][i];
if (a == b) return a;
for (int i = 19; i >= 0; i--) if (lift[a][i] != lift[b][i]){
a = lift[a][i];
b = lift[b][i];
}
return lift[a][0];
}
void updlazy(int l, int r, int pos){
seg[pos] += lazy[pos] * (r - l + 1);
if (l == r){
lazy[pos] = 0;
return;
}
lazy[pos * 2] += lazy[pos];
lazy[pos * 2 + 1] += lazy[pos];
lazy[pos] = 0;
return;
}
void upd(int l, int r, int pos, int ql, int qr, int v){
if (lazy[pos] != 0) updlazy(l, r, pos);
if (l >= ql && r <= qr){
seg[pos] += (r - l + 1) * v;
if (l == r) return;
lazy[pos * 2] += v;
lazy[pos * 2 + 1] += v;
}
else if (l > qr || r < ql) return;
else {
int mid = (l + r)/2;
upd(l, mid, pos*2, ql, qr, v);
upd(mid + 1, r, pos*2 + 1, ql, qr, v);
seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
}
int query(int l, int r, int pos, int qp){
if (lazy[pos] != 0) updlazy(l, r, pos);
if (l == r) return seg[pos];
int mid = (l + r)/2;
if (qp <= mid) return query(l, mid, pos*2, qp);
else return query(mid + 1, r, pos*2 + 1, qp);
}
int querypath(int a, int b, int lc){
return query(1, n, 1, tin[a]) + query(1, n, 1, tin[b]) - 2 * query(1, n, 1, tin[lc]);
}
void pbs(){
for (int i = 1; i <= m; i++) work[i].clear();
for (int i = 1; i <= 4 * n; i++) seg[i] = lazy[i] = 0;
for (int i = 1; i <= q; i++){
if (Q[i].l == Q[i].r) continue;
int m = (Q[i].l + Q[i].r + 1)/2;
work[m].push_back(i);
}
for (int i = 1; i <= m; i++){
upd(1, n, 1, tin[C[i].a], tout[C[i].a], C[i].c);
for (auto x : work[i]){
int val = querypath(Q[x].a, Q[x].b, Q[x].lc);
if (val > Q[x].silver) Q[x].r = i - 1;
else Q[x].l = i;
}
}
}
bool comp(check a, check b){
return a.c < b.c;
}
void Solve()
{
cin >> n >> m >> q;
vector <pair<int, int>> e;
for (int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
e.push_back({u, v});
}
dfs(1, -1);
for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) lift[i][j] = lift[lift[i][j - 1]][j - 1];
for (int i = 1; i <= m; i++){
int p, c; cin >> p >> c;
--p;
if (dep[e[p].f] > dep[e[p].s]) C[i].a = e[p].f;
else C[i].a = e[p].s;
C[i].c = c;
}
sort(C + 1, C + m + 1, comp);
for (int i = 1; i <= q; i++){
int a, b, x, y; cin >> a >> b >> x >> y;
Q[i].a = a;
Q[i].b = b;
Q[i].gold = x;
Q[i].silver = y;
Q[i].i = i;
Q[i].lc = findlca(a, b);
Q[i].l = 0;
Q[i].r = m;
}
for (int it = 0; it < 20; it++){
pbs();
}
for (int i = 1; i <= m; i++) work[i].clear();
for (int i = 1; i <= 4 * n; i++) seg[i] = lazy[i] = 0;
for (int i = 1; i <= q; i++){
assert(Q[i].l == Q[i].r);
if (Q[i].l == m){
Q[i].need = 0;
} else {
work[Q[i].l + 1].push_back(i);
}
}
for (int i = m; i >= 1; i--){
upd(1, n, 1, tin[C[i].a], tout[C[i].a], 1);
for (auto x : work[i]){
Q[x].need = querypath(Q[x].a, Q[x].b, Q[x].lc);
}
}
for (int i = 1; i <= q; i++){
int x = i;
if (Q[x].need > Q[x].gold) cout << "-1\n";
else cout << Q[x].gold - Q[x].need << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |