이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define lg long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2
const lg N = 1e5+5;
vector<lg> adj[N], o[N];
vector<array<lg, 2>> updates(N);
lg euler[N], depth[N], anc[N][20], in[N], out[N], tmp, bit1[N], bit2[N], edges[N][2], que[N][4], low[N], high[N], best[N], ans[N];
lg n, m, q;
/*
BIT: sum, cnt
queries: st, en, gold, silver
*/
void dfs(lg src)
{
in[src] = ++tmp;
euler[in[src]] = src;
for(auto it : adj[src])
{
if(anc[src][0] == it) continue;
anc[it][0] = src;
for(int i = 1; i < 20; i++)
{
if(anc[it][i-1] == -1) break;
anc[it][i] = anc[anc[it][i-1]][i-1];
}
depth[it] = depth[src]+1;
dfs(it);
}
out[src] = tmp;
}
lg lca(lg a, lg b)
{
if(depth[a] > depth[b]) swap(a, b);
for(int i = 19; i+1; i--)
{
if(anc[b][i] == -1 || depth[anc[b][i]] < depth[a]) continue;
b = anc[b][i];
}
if(a == b) return a;
for(int i = 19; i+1; i--)
{
if(anc[a][i] == -1 || anc[a][i] == anc[b][i]) continue;
a = anc[a][i];
b = anc[b][i];
}
return anc[a][0];
}
void update(lg idx, lg val)
{
for(; idx <= n; idx += (idx&(-idx)))
{
bit1[idx] += val;
bit2[idx] += (val < 0 ? -1 : 1);
}
return;
}
lg get(lg idx, lg t)
{
lg a = 0;
for(; idx; idx -= (idx&(-idx))) a += (t ? bit1[idx] : bit2[idx]);
return a;
}
int main()
{
fastio;
cin >> n >> m >> q;
for(int i = 1; i < n; i++)
{
lg u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
edges[i][0] = u;
edges[i][1] = v;
}
memset(anc, -1, sizeof(anc));
dfs(1);
for(int i = 1; i < n; i++)
{
if(depth[edges[i][0]] > depth[edges[i][1]]) swap(edges[i][0], edges[i][1]);
}
for(int i = 1; i <= m; i++)
{
lg a, b;
cin >> a >> b;
updates[i][0] = b;
updates[i][1] = a;
}
sort(updates.begin()+1, updates.begin()+m+1);
for(int i = 0; i < q; i++)
{
for(int j = 0; j < 4; j++) cin >> que[i][j];
low[i] = 0, high[i] = m;
}
bool changed = true;
while(changed)
{
changed = false;
for(int i = 1; i <= n; i++) bit1[i] = bit2[i] = 0;
for(int i = 0; i < q; i++)
{
if(low[i] <= high[i]) o[(low[i]+high[i]) >> 1].push_back(i);
}
for(int i = 0; i <= m; i++)
{
if(i)
{
update(in[edges[updates[i][1]][1]], updates[i][0]);
update(out[edges[updates[i][1]][1]]+1, -updates[i][0]);
}
while(o[i].size())
{
changed = true;
lg idx = o[i].back();
o[i].pop_back();
lg _lca = lca(que[idx][0], que[idx][1]);
lg x = get(in[que[idx][0]], 1)+get(in[que[idx][1]], 1)-2*get(in[_lca], 1);
if(x <= que[idx][3])
{
low[idx] = i+1;
best[idx] = i;
}
else{
high[idx] = i-1;
}
}
}
}
for(int i = 1; i <= n; i++) bit1[i] = bit2[i] = 0;
for(int i = 0; i < q; i++) o[best[i]].push_back(i);
for(int i = 1; i <= m; i++)
{
update(in[edges[updates[i][1]][1]], updates[i][0]);
update(out[edges[updates[i][1]][1]]+1, -updates[i][0]);
while(o[i].size())
{
lg idx = o[i].back();
o[i].pop_back();
lg _lca = lca(que[idx][0], que[idx][1]);
lg x = get(in[que[idx][0]], 0)+get(in[que[idx][1]], 0)-2*get(in[_lca], 0);
ans[idx] = -x;
}
}
for(int i = 0; i < q; i++)
{
lg _lca = lca(que[i][0], que[i][1]);
lg x = get(in[que[i][0]], 0)+get(in[que[i][1]], 0)-2*get(in[_lca], 0);
ans[i] += x;
}
for(int i = 0; i < q; i++)
{
if(ans[i] > que[i][2]) cout << "-1\n";
else cout << que[i][2]-ans[i] << '\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... |