| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1143633 | Der_Vlapos | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>
#include <bits/stdc++.h>
#include <chrono>
#include <random>
// @author: Vlapos
namespace operators
{
template <typename T1, typename T2>
std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
{
in >> x.first >> x.second;
return in;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
{
out << x.first << " " << x.second;
return out;
}
template <typename T1>
std::istream &operator>>(std::istream &in, std::vector<T1> &x)
{
for (auto &i : x)
in >> i;
return in;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
}
// name spaces
using namespace std;
using namespace operators;
// end of name spaces
// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines
// usefull stuff
void boost()
{
ios_base ::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }
const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};
const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;
#define int ll
struct segTreeSum
{
vector<ll> tree;
int sz;
void init(int n)
{
sz = n;
tree.resize(2 * sz);
}
void build(vector<int> &a)
{
init(a.size());
for (int i = 0; i < a.size(); ++i)
tree[i + sz] = a[sz];
for (int i = sz - 1; i > 0; --i)
tree[i] = tree[i << 1] + tree[(i << 1) + 1];
}
int get(int l, int r) // [l, r)
{
l += sz;
r += sz;
int res = 0;
while (l < r)
{
if (l & 1)
res += tree[l++];
if (r & 1)
res += tree[--r];
l >>= 1;
r >>= 1;
}
return res;
}
void add(int pos, int val)
{
pos += sz;
tree[pos] += val;
pos >>= 1;
while (pos)
{
tree[pos] = tree[pos << 1] + tree[(pos << 1) + 1];
pos >>= 1;
}
}
};
struct test
{
vector<vector<pii>> tree;
vector<vector<int>> jump;
vector<int> tin, tout, edgeV, ans;
int timer = 0;
segTreeSum ecnt, esum;
void dfs(int v, int pr = -1)
{
tin[v] = timer++;
for (auto [tov, id] : tree[v])
if (tov != pr)
{
jump[tov][0] = v;
for (int k = 1; k < 20; ++k)
jump[tov][k] = jump[jump[tov][k - 1]][k - 1];
edgeV[id] = tov;
dfs(tov, v);
}
tout[v] = timer++;
}
bool isP(int pr, int v)
{
return tin[pr] <= tin[v] and tout[v] <= tout[pr];
}
int lca(int v, int u)
{
if (isP(v, u))
return v;
if (isP(u, v))
return u;
for (int k = 19; k >= 0; --k)
if (!isP(jump[v][k], u))
v = jump[v][k];
return jump[v][0];
}
void solve(vector<pair<pii, pii>> &qrs, vector<pii> &els, int &u, int L, int R)
{
int M = (L + R) >> 1;
// move u to M
{
while (u < M)
{
int v = edgeV[els[u].s];
ecnt.add(tin[v], 1);
ecnt.add(tout[v], -1);
esum.add(tin[v], els[u].f);
esum.add(tout[v], -els[u].f);
u++;
}
while (u > M)
{
u--;
int v = edgeV[els[u].s];
ecnt.add(tin[v], -1);
ecnt.add(tout[v], 1);
esum.add(tin[v], -els[u].f);
esum.add(tout[v], els[u].f);
}
}
vector<pair<pii, pii>> win, lose;
for (auto [bf1, bf2] : qrs)
{
auto [id, c] = bf1;
auto [v, u] = bf2;
int sum = esum.get(0, tin[v] + 1) + esum.get(0, tin[u] + 1) - 2 * esum.get(0, tin[lca(v, u)] + 1);
if (sum <= c)
{
win.pb({bf1, bf2});
ans[id] = ecnt.get(0, tin[v] + 1) + ecnt.get(0, tin[u] + 1) - 2 * ecnt.get(0, tin[lca(v, u)] + 1);
}
else
{
lose.pb({bf1, bf2});
}
}
qrs.clear();
qrs.shrink_to_fit();
if (R - L > 1)
{
solve(lose, els, u, L, M);
solve(win, els, u, M, R);
}
else
assert(lose.size() == 0);
}
void solve(int testcase)
{
boost();
int n, m, q;
cin >> n >> m >> q;
ecnt.init(n * 2);
esum.init(n * 2);
ans.resize(q);
tree.resize(n);
tin.resize(n);
tout.resize(n);
jump.resize(n, vector<int>(20));
edgeV.resize(n - 1, 0);
for (int i = 0; i < n - 1; ++i)
{
int x, y;
cin >> x >> y;
--x, --y;
tree[x].pb({y, i});
tree[y].pb({x, i});
}
dfs(0);
vector<pii> els;
for (int i = 0; i < m; ++i)
{
int p, c;
cin >> p >> c;
--p;
els.pb({c, p});
}
sort(all(els));
vector<int> S(q), T(q), X(q), Y(q);
vector<pair<pii, pii>> qrs;
for (int i = 0; i < q; ++i)
{
cin >> S[i] >> T[i] >> X[i] >> Y[i];
--S[i];
--T[i];
qrs.pb({{i, Y[i]}, {S[i], T[i]}});
}
int u = 0;
solve(qrs, els, u, 0, els.size() + 1);
assert(u == els.size());
for (int i = 0; i < q; ++i)
{
int v = S[i];
int u = T[i];
int cntNeeded = ecnt.get(0, tin[v] + 1) + ecnt.get(0, tin[u] + 1) - 2 * ecnt.get(0, tin[lca(v, u)] + 1) - ans[i];
cout << max(X[i] - cntNeeded, -1) << "\n";
}
}
};
main()
{
boost();
int q = 1;
// cin >> q;
for (int i = 0; i < q; i++)
{
test t;
t.solve(i);
}
return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
// //
// Coded by Der_Vlapos //
// //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//