//####################
//TwoCurrencies
//####################
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const int maxiN = 1000042;
const int LOG = 18;
int n, m, q;
vector < int > links[maxiN];
int depth[maxiN];
int up[maxiN][LOG];
void root(int node, int d = 0, int parent = -1) {
up[node][0] = parent;
depth[node] = d;
for (int v: links[node])
if (v != parent) {
root(v, d + 1, node);
}
}
int getK(int node, int K) {
for (int i = LOG - 1; i >= 0; i--) {
if ((K >> i) & 1) {
node = up[node][i];
}
}
return node;
}
int LCA(int a, int b) {
if (depth[b] > depth[a]) swap(a, b);
a = getK(a, depth[a] - depth[b]);
if (a == b) {
return a;
}
for (int l = LOG - 1; l >= 0; l--) {
if (up[a][l] != up[b][l]) {
a = up[a][l];
b = up[b][l];
}
}
return up[a][0];
}
pair<int,int> eulerseg[maxiN];
int actEuleur=-1;
void computeEuleurTour(int node,int parent = -1){
actEuleur++;
eulerseg[node].first = actEuleur;
for(int v:links[node])if(parent!=v){
computeEuleurTour(v,node);
}
actEuleur++;
eulerseg[node].second = actEuleur;
}
template<typename T>
struct segtree{
vector<T> vals;
int leaf;
segtree(int n){
leaf = (1<<((int)ceil(log2(n))));
vals.resize(2*leaf);
fill(vals.begin(),vals.end(),0);
}
segtree()=default;
void init(int n){
leaf = (1<<((int)ceil(log2(n))));
vals.resize(2*leaf);
fill(vals.begin(),vals.end(),0);
}
void reset(){
fill(vals.begin(),vals.end(),0);
}
void _addRange(int a,int b,T val){
if(a==b){
vals[a]+=val;
}else if(a&1){
vals[a]+=val;
_addRange(a+1,b,val);
}else if(b%2==0){
vals[b]+=val;
_addRange(a,b-1,val);
}else{
_addRange(a/2,b/2,val);
}
}
void addRange(int a,int b,T val){
_addRange(a+leaf,b+leaf,val);
}
T getVal(int pos){
pos+=leaf;
int re = 0;
for(int p=pos;p>=1;p>>=1){
re+=vals[p];
}
return re;
}
};
struct req{
int a,b;
ll x,y;
int lca;
ll totalSum;
};
vector<pair<ll,int>> W_child;
vector<req> queries;
vector<pair<ll,int>> ans;
struct node{
int deb,fin;
vector<int> id_req;
};
int middle(node&node_){
int m = (node_.deb+node_.fin)/2;
if(m==node_.fin)m=node_.deb;
return m;
}
segtree<ll> pathsum;
segtree<int> occurence;
pair<ll,int> computePath(int a,int b,int lca){
ll nbocc=0;
ll sumGold=0;
if(a==lca && b==lca){
nbocc=0;
}else if(a==lca){
nbocc=occurence.getVal(eulerseg[b].first)-occurence.getVal(eulerseg[a].first);
sumGold=pathsum.getVal(eulerseg[b].first)- pathsum.getVal(eulerseg[a].first);
}else if(b==lca){
nbocc=occurence.getVal(eulerseg[a].first)-occurence.getVal(eulerseg[b].first);
sumGold=pathsum.getVal(eulerseg[a].first)- pathsum.getVal(eulerseg[b].first);
}else{
nbocc=occurence.getVal(eulerseg[b].first)+occurence.getVal(eulerseg[a].first)-2*occurence.getVal(eulerseg[lca].first);;
sumGold=pathsum.getVal(eulerseg[b].first)+ pathsum.getVal(eulerseg[a].first)- 2*pathsum.getVal(eulerseg[lca].first);;
}
return {sumGold,nbocc};
}
vector<bool> oracle(vector<int> reqs,int p){
vector<bool> bans(reqs.size());
for(int i=0;i<reqs.size();i++){
pair<ll,int> rep = computePath(queries[reqs[i]].a,queries[reqs[i]].b,queries[reqs[i]].lca);
if(queries[reqs[i]].x>=rep.second && queries[reqs[i]].y>=(queries[reqs[i]].totalSum-rep.first)){
bans[i]=true;
}else{
bans[i]=false;
}
}
return bans;
}
void parallel_binary_search(){
//usagé donc on nettoie
pathsum.reset();
occurence.reset();
vector<int> ids;
for(int i = 0;i<q;i++){
ids.push_back(i);
}
node first = {0,m,ids};
vector<node> nodes = {first};
for(int lvl=0;lvl<LOG;lvl++){
pathsum.reset();
occurence.reset();
int actPush = m;
vector<node> next_lvl;
if(nodes.size()){
for(node &node_:nodes){
if(node_.id_req.empty())continue;
int mid = middle(node_);
if(mid>actPush){
cerr<<"error !"<<endl;
}
while(actPush>mid){
actPush--;
pathsum.addRange(eulerseg[W_child[actPush].second].first,eulerseg[W_child[actPush].second].second,W_child[actPush].first);
occurence.addRange(eulerseg[W_child[actPush].second].first,eulerseg[W_child[actPush].second].second,1);
}
vector<bool> dir = oracle(node_.id_req,mid);
node left,right;
left.deb = node_.deb;
left.fin = mid;
right.deb = mid+1;
right.fin = node_.fin;
for(int i = 0;i<node_.id_req.size();i++){
if(dir[i]){
if(node_.deb!=node_.fin){
right.id_req.push_back(node_.id_req[i]);
}
ans[node_.id_req[i]] = computePath(queries[node_.id_req[i]].a,queries[node_.id_req[i]].b,queries[node_.id_req[i]].lca);
}else{
if(node_.deb!=node_.fin){
left.id_req.push_back(node_.id_req[i]);
}
}
}
next_lvl.push_back(right);
next_lvl.push_back(left);
}
swap(nodes,next_lvl);
}else{
break;
}
}
}
signed main() {
fill(depth, depth + maxiN, -1);
cin >> n >> m >> q;
queries.resize(q);
occurence.init(2*n);
pathsum.init(2*n);
ans.resize(q);
for(int i = 0;i<q;i++)ans[i] = {-1,-1};
vector < pair < int, int >> edges;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
edges.push_back({a,b});
links[a].push_back(b);
links[b].push_back(a);
}
root(0, 0, -1);
int C=-1;
computeEuleurTour(0);
for (int i = 0; i < m; i++) {
int p, c;
cin >> p >> c;
C = c;
p--;
auto a = edges[p].first;
auto b = edges[p].second;
if (depth[a] < depth[b]) swap(a, b);
occurence.addRange(eulerseg[a].first,eulerseg[a].second,1);
pathsum.addRange(eulerseg[a].first,eulerseg[a].second,C);
W_child.push_back({c,a});
}
sort(W_child.begin(),W_child.end());
//On calcule la tab de LCA
for (int l = 1; l < LOG; l++) {
for (int i = 0; i < n; i++) {
if (up[i][l - 1] == -1) {
up[i][l] = -1;
}
up[i][l] = up[up[i][l - 1]][l - 1];
}
}
for (int i = 0; i < q; i++) {
int a,b;
ll x, y;
cin >> a >> b >> x >> y;
a--;
b--;
int lca = LCA(a, b);
queries[i] = {a,b,x,y,lca,computePath(a,b,lca).first};
}
pathsum.reset();
occurence.reset();
vector<int> req;for(int i = 0;i<q;i++)req.push_back(i);
for(int borne = m;borne>=0;borne--){
if(borne!=m){
pathsum.addRange(eulerseg[W_child[borne].second].first,eulerseg[W_child[borne].second].second,W_child[borne].first);
occurence.addRange(eulerseg[W_child[borne].second].first,eulerseg[W_child[borne].second].second,1);
}
vector<bool> dir = oracle(req,borne);
for(int i = 0;i<q;i++){
if(dir[i] && ans[i].first==-1 && ans[i].second==-1){
ans[i] = computePath(queries[i].a,queries[i].b,queries[i].lca);
}
}
}
//parallel_binary_search();
for(int i = 0;i<q;i++){
ll tot = queries[i].totalSum-ans[i].first;
if(ans[i].first==-1 && ans[i].second==-1){
cout<<-1<<'\n';
continue;
}
if(queries[i].x>=ans[i].second && queries[i].y>=tot){
cout<<queries[i].x-ans[i].second<<'\n';
}else{
cout<<-1<<'\n';;
}
}
return 0;
};
Compilation message
currencies.cpp: In function 'std::vector<bool> oracle(std::vector<int>, int)':
currencies.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i=0;i<reqs.size();i++){
| ~^~~~~~~~~~~~
currencies.cpp: In function 'void parallel_binary_search()':
currencies.cpp:189:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for(int i = 0;i<node_.id_req.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
30040 KB |
Output is correct |
| 2 |
Correct |
9 ms |
30040 KB |
Output is correct |
| 3 |
Correct |
8 ms |
29892 KB |
Output is correct |
| 4 |
Correct |
9 ms |
29788 KB |
Output is correct |
| 5 |
Incorrect |
119 ms |
30552 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
30040 KB |
Output is correct |
| 2 |
Incorrect |
216 ms |
30300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
29784 KB |
Output is correct |
| 2 |
Incorrect |
166 ms |
30552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
30040 KB |
Output is correct |
| 2 |
Correct |
9 ms |
30040 KB |
Output is correct |
| 3 |
Correct |
8 ms |
29892 KB |
Output is correct |
| 4 |
Correct |
9 ms |
29788 KB |
Output is correct |
| 5 |
Incorrect |
119 ms |
30552 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
