Submission #914916

#	Time	Username	Problem	Language	Result	Execution time	Memory
914916		ThylOne	Two Currencies (JOI23_currencies)	C++14	10 / 100	653 ms	175040 KiB

currencies

//####################
//TwoCurrencies
//####################
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxiN = 1000000;
const int LOG = 17;
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];
}
map<int,vector<int>> peages;
vector<int> val[maxiN];
signed main(){
    fill(depth,depth+maxiN,-1);
    int n,m,q;cin>>n>>m>>q;
    vector<pair<int,int>> edges;
    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        edges.push_back(make_pair(a,b));
        links[a].push_back(b);
        links[b].push_back(a);
    }
    root(0,0,-1);
    int C;
    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);
        peages[c].push_back(a);
        val[a].push_back(c);
    }
    //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,x,y;cin>>a>>b>>x>>y;
        a--;b--;
        int lca = LCA(a,b);
        int ans = 0;
        if(lca==a){
            swap(a,b);
        }
        set<int> S;
        auto f = [&](int l){
            for(int j=l;j!=-1 && j!=lca;j=up[j][0])
                S.insert(j);
        };
        f(a);
        f(b);
        vector<int> vec;
        for(auto x:S){
            for(auto v:val[x]){
                vec.push_back(v);
            }
        }
        
        
        
        
        sort(vec.begin(),vec.end());
        int cnt=0;

        for(int j = 0;j<vec.size() && y>=vec[j];j++){
            y -= vec[j];
            cnt++;
        }
        if((vec.size()-cnt)>x){
            cout<<-1<<'\n';
        }else{
            cout<<x-(vec.size()-cnt)<<endl;
        }
        
        
        
    }

    return 0;
};

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:103:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0;j<vec.size() && y>=vec[j];j++){
      |                       ~^~~~~~~~~~~
currencies.cpp:107:28: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
  107 |         if((vec.size()-cnt)>x){
      |            ~~~~~~~~~~~~~~~~^~
currencies.cpp:79:13: warning: unused variable 'ans' [-Wunused-variable]
   79 |         int ans = 0;
      |             ^~~
currencies.cpp:55:9: warning: variable 'C' set but not used [-Wunused-but-set-variable]
   55 |     int C;
      |         ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32