| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890761 | Cyber_Wolf | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, seg[N << 2][2], edges[N][2], que[N][4], low[N], high[N], best[N], cnt[N];
/*
segtree: 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 build(lg node, lg lr, lg hr)
{
if(lr == hr)
{
seg[node][0] = 0;
seg[node][1] = 0;
return;
}
build(node << 1, lr, mid);
build(node << 1 | 1, mid+1, hr);
seg[node][0] = 0;
seg[node][1] = 0;
}
void update(lg node, lg lr, lg hr, lg idx, lg val)
{
if(idx > hr || lr > idx) return;
if(lr == hr)
{
seg[node][0] += val;
seg[node][1]++;
return;
}
update(node << 1, lr, mid, idx, val);
update(node << 1 | 1, mid+1, hr, idx, val);
seg[node][0] = seg[node << 1][0]+seg[node << 1 | 1][0];
seg[node][1] = seg[node << 1][1]+seg[node << 1 | 1][1];
return;
}
array<lg, 2> get(lg node, lg lr, lg hr, lg lq, lg hq)
{
if(lq > hr || lr > hq) return {0, 0};
if(lq <= lr && hr <= hq) return {seg[node][0], seg[node][1]};
array<lg, 2> ab = get(node << 1, lr, mid, lq, hq);
array<lg, 2> cd = get(node << 1 | 1, mid+1, hr, lq, hq);
ab[0] += cd[0];
ab[1] += cd[1];
return ab;
}
int main()
{
fastio;
lg n, m, q;
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;
build(1, 1, n);
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(1, 1, n, in[edges[updates[i][1]][1]], updates[i][0]);
update(1, 1, n, 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]);
array<lg, 2> ab = get(1, 1, n, in[que[idx][0]], out[que[idx][0]]);
array<lg, 2> cd = get(1, 1, n, in[que[idx][1]], out[que[idx][1]]);
array<lg, 2> ef = get(1, 1, n, in[_lca], out[_lca]);
if(cost <= que[idx][3])
{
if(low[idx] != i+1) changed = true;
low[idx] = i+1;
best[idx] = i;
}
else{
if(high[idx] != i-1) changed = true;
high[idx] = i-1;
}
}
}
}
for(int i = 0; i <= m; i++)
{
}
for(int i = 0; i < q; i++)
{
}
return 0;
}