| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 912696 | Pentagonal | 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.
// #pragma GCC target("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
//#pragma GCC -Wnarrowing
//Template {
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//IO templates
//Note: use endl only for interactive problems or to debug segfaults; use newl for other problems
#define newl "\n"
#define fastIO ios::sync_with_stdio(false); cin.tie(nullptr)
#define fileIO(x) ifstream fin((str) x + (str) ".in"); ofstream fout((str) x + (str) ".out");
// void fileIO(string x) {}
#define flush() fflush(stdout)
#define interact(n) fflush(stdout); cin >> n; if (n == -1) return 0
#define testcases int tt; cin >> tt; fun (i, tt) solve();
#define edgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addEdges(a, b);}
#define WeightedEdgeIO(m) fun (i, m) {int a, b, c; cin >> a >> b >> c; addWeightedEdges(a, b, c);}
#define numberedEdgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addWeightedEdges(a, b, i);}
//types
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define ld long double
#define str string
#define boolean bool
#define String string
//vector
#define pb push_back
#define append push_back
//pairs
#define mp make_pair
#define p2 pair<int, int>
#define p3 pair<int, p2>
#define m3(x, y, z) mp(x, mp(y, z))
#define ich first
#define ni second.first
#define sanshi second.second
//For loops
#define ahegao(i, a, b) for (int i = a; i < b; i++)
#define baka(i, b, a) for (int i = b; i > a; i--)
#define fun(i, n) for (int i = 1; i <= (n); (i)++)
#define fon(i, n) for (int i = 0; i < (n); (i)++)
#define fur(i, n) for (auto i : (n))
#define oniichan(i, n) for (auto &i : (n))
//Sorts
#define sz(aaa) ((signed) aaa.size())
// #define len(aaa) ((signed) aaa.size())
#define all(a) a.begin(), a.end()
#define Sort(a) sort((a).begin(), (a).end())
#define rSort(a) sort((a).rbegin(), (a).rend())
#define clamp(x, y) (x) = min((int) (x), (int) (y))
#define CLAMP(x, y) (x) = max((int) (x), (int) (y))
//Other stuff
#define pqueue priority_queue
#define elif else if
#define addEdges(a, b) adj[a].pb(b); adj[b].pb(a)
#define addWeightedEdges(a, b, c) adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c))
// #define find find_by_order
#define printLength(x) if (x < INF) cout << x << newl; else cout << -1 << newl;
// #define printVector(a) fur (i, a) cout << i << ' '; cout << newl;
void printVector(vector<int> DontUseThisName) {
fur (i, DontUseThisName) cout << i << ' '; cout << newl;
}
void printVector(vector<p2> DontUseThisName) {
fur (i, DontUseThisName) cout << i.first << ' ' << i.second << newl; cout << newl;
}
void printVector(vector<vector<int>> DontUseThisName) {
fur (i, DontUseThisName) printVector(i); cout << newl;
}
void pv(int a) {cout << a << newl;}
void pv(int a, int b) {printVector({a, b});}
void pv(p2 a) {printVector({a.first, a.second});};
void pv(int a, int b, int c) {printVector({a, b, c});}
void pv(int a, int b, int c, int d) {printVector({a, b, c, d});}
void pv(int a, int b, int c, int d, int e) {printVector({a, b, c, d, e});}
void pv(int a, int b, int c, int d, int e, int f) {printVector({a, b, c, d, e, f});}
// void pv(int a, )
// void printVector(vector<char> DontUseThisName) {
// fur (i, DontUseThisName) cout << i << ' '; cout << newl;
// }
// void printRange(vector<int>::iterator Left, vector<int>::iterator Right) {
// for (auto i = Left; i < Right; i++) cout << *i << ' ';
// cout << newl;
// }
//Constants
const int MOD = 1e9+7; // 998244353
// const int SMALLMOD = 998244353;
const int INF = 2e9+1337;
const ll EXCEED = 2e18+1337;
const ll GRAVITY = 8e18;
//#define vectorIO(n, MikuBondage) fun (j, n) {int i; cin >> i; MikuBondage.pb(i);}
void vectorIO(int n, vector<int> &DontUseThisName) {
fun (j, n) {int i; cin >> i; DontUseThisName.pb(i);}
}
//#define vector2IO(n, MikuBondage) fun (j, n) {int i, ii; cin >> i >> ii; MikuBondage.pb(mp(i, ii));}
void vector2IO(int n, vector<p2> &DontUseThisName) {
fun (j, n) {int i, ii; cin >> i >> ii; DontUseThisName.pb(mp(i, ii));}
}
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
#define shortest_path_queue priority_queue<p2, vector<p2>, greater<p2>>
#define printArray(DontUseThisName, NakedLolisGalore, GenshinImpactClimbing) ahegao (j, NakedLolisGalore, GenshinImpactClimbing + 1) cout << DontUseThisName[j] << ' '; cout << newl;
#define print2dArray(SplitComplexProblemsIntoMultipleParts, ScuteSwarm, GenshinImpactClimbing) fun (i, ScuteSwarm) {fun (j, GenshinImpactClimbing) cout << SplitComplexProblemsIntoMultipleParts[i][j] << ' '; cout << newl;}
//}
// #define debugModifiedGraph
// #define debugLCA
// #define debugBIT
const int MAX = 200005;
vector<int> cost[MAX];
vector<p2> adj[MAX], adj2[MAX];
int pos[MAX], sparse[MAX][19], lower[MAX], upper[MAX], depth[MAX], weight[MAX], val[MAX], to[MAX], from[MAX], l[MAX], r[MAX], maxGold[MAX], maxSilver[MAX], res[MAX];
bool done[MAX];
vector<p2> ord, MikuBondage, lll;
int n, m, q, curr, temp;
void dfs1(int x, int from, int k) {
pos[x] = k;
fur (i, adj[x]) if (i.first != from) {
if (cost[i.second].empty()) dfs1(i.first, x, k);
else {
curr += 1;
adj2[k].pb({curr, i.second});
adj2[curr].pb({k, i.second});
dfs1(i.first, x, curr);
}
}
}
void dfs2(int x, int from, int dist) {
temp++;
depth[x] = dist;
sparse[temp][0] = x;
lower[x] = temp;
fur (i, adj2[x]) if (i.first != from) {
dfs2(i.first, x, dist + sz(cost[i.second]));
fur (j, cost[i.second]) {
ord.pb({j, i.first});
#ifdef debugModifiedGraph
weight[i.first] += j;
#endif
}
temp++;
sparse[temp][0] = x;
}
upper[x] = temp;
}
bool check(int a, int b) {
return depth[a] < depth[b];
}
void buildSparseTable() {
#ifdef debugLCA
fun (i, temp) cout << sparse[i][0] << ' ';
#endif
fun (k, 18) {
#ifdef debugLCA
cout << newl;
#endif
fun (i, temp - (1 << k) + 1) {
sparse[i][k] = min(sparse[i][k-1], sparse[i + (1 << (k - 1))][k-1], check);
#ifdef debugLCA
cout << sparse[i][k] << ' ';
#endif
}
}
}
int lca(int l, int r) {
#ifdef debugLCA
pv(l, r, lower[l], lower[r]);
#endif
l = lower[l];
r = lower[r];
if (l > r) swap(l, r);
int j = 1;
while ((1 << j) < r - l + 1) j++;
j--;
return(min(sparse[l][j], sparse[r - (1 << j) + 1][j], check));
}
inline int query(int x) {
if (x == 0) return 0;
x = lower[x];
int _curr = 0, _res = 0;
baka (i, 18, -1) if (x & (1 << i)) {
_curr += (1 << i);
_res += val[_curr];
// pv(curr, i, val[curr]);
}
return _res;
}
inline void modify(int x, int k) {
int i = 0;
while (x < MAX) {
val[x] += k;
// pv(x, k);
// x = x - (x % (1 << i)) + (1 << i) * ;
while ((x & (1 << i)) == 0) i++;
x += (1 << i);
}
}
signed main() {
fastIO;
cin >> n >> m >> q;
numberedEdgeIO(n-1);
fun (i, m) {
int a, b; cin >> a >> b;
cost[a].pb(b);
}
curr = 1;
dfs1(1, -1, 1);
// {
dfs2(1, -1, 1);
#ifdef debugModifiedGraph
printArray(pos, 1, n);
printArray(weight, 1, curr);
printArray(depth, 1, curr);
fun (i, curr) fur (j, adj2[i]) if (i < j.first) pv(i, j.first);
#endif
// }
buildSparseTable();
// {
#ifdef debugLCA
pv(lca(4, 5));
#endif
// }
// printVector(ord);
Sort(ord);
fun (i, q) {
cin >> to[i] >> from[i] >> maxGold[i] >> maxSilver[i];
to[i] = pos[to[i]];
from[i] = pos[from[i]];
l[i] = 0;
r[i] = sz(ord);
}
bool finished = false;
while (not finished) {
finished = true;
fun (i, q) {
if (not done[i]) {
if (l[i] < r[i]) {
int mid = (l[i] + r[i] + 1) / 2;
// pv(l[i], r[i], mid);
MikuBondage.pb({mid, i});
finished = false;
} else {
// pv(i, l[i]);
lll.pb({l[i], i});
done[i] = true;
}
}
}
memset(val, 0, (temp + 2) * sizeof(int));
Sort(MikuBondage);
int pointer = 0;
fur (rozalinBestWaifu, MikuBondage) {
int t = rozalinBestWaifu.first;
int i = rozalinBestWaifu.second;
while (pointer < t) {
modify(lower[ord[pointer].second], ord[pointer].first);
modify(upper[ord[pointer].second] + 1, -ord[pointer].first);
// {
#ifdef debugBIT
pv(ord[pointer]);
pv(lower[ord[pointer].second], upper[ord[pointer].second]);
printArray(val, 1, 16);
#endif
// }
pointer++;
}
// pv(i, t, from[i], query(from[i]), to[i], query(to[i]));
// pv(lca(from[i], to[i]), query(lca(from[i], to[i])), maxSilver[i]);
if (query(from[i]) + query(to[i]) - 2 * query(lca(from[i], to[i])) <= maxSilver[i]) {
l[i] = t;
} else {
r[i] = t - 1;
}
}
// break;
MikuBondage.clear();
}
memset(val, 0, (temp + 2) * sizeof(int));
Sort(lll);
int pointer = 0;
fur (rozalinBestWaifu, lll) {
int t = rozalinBestWaifu.first;
int i = rozalinBestWaifu.second;
while (pointer < t) {
modify(lower[ord[pointer].second], 1);
modify(upper[ord[pointer].second] + 1, -1);
// {
#ifdef debugBIT
pv(ord[pointer]);
pv(lower[ord[pointer].second], upper[ord[pointer].second]);
printArray(val, 1, 16);
#endif
// }
pointer++;
}
res[i] = max(maxGold[i] - depth[from[i]] - depth[to[i]] + 2 * depth[lca(from[i], to[i])]
+ (query(from[i]) + query(to[i]) - 2 * query(lca(from[i], to[i]))), -1);
}
fun (i, q) cout << res[i] << newl;
}