Submission #1116997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116997		salmon	Two Currencies (JOI23_currencies)	C++14	0 / 100	20 ms	10576 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#define pb(x) push_back(x)

struct node{

    int s,e,m;
    long long int lazy = 0;
    node *l,*r;

    node(int S, int E){
        s = S;
        e = E;
        m = (s + e)/2;

        lazy = 0;

        if(s != e){
            l = new node(s,m);
            r = new node(m + 1, e);
        }
    }

    void update(int S, int E, int k){
        if(S <= s && e <= E){
            lazy += k;
            return;
        }

        if(S <= m){
            l -> update(S,E,k);
        }
        if(m < E){
            r -> update(S,E,k);
        }
    }

    long long int query(int i){
        if(s == e) return lazy;

        if(i <= m) return lazy + l -> query(i);
        if(m < i) return lazy + r -> query(i);
    }

}*root,*ront,*poot;

struct peep{
    int s;
    int e;
    int m;
    int i;
};

int N;
int M;
int u,v;
vector<int> adjlst[100100];
int pre[100100];
int post[100100];
int cont = 0;
int parent[100100][30];
vector<pair<int,int>> edge;
int p,c;
long long int g,s;
vector<pair<int,int> > update;
vector<pair<pair<int,int>,pair<int,long long int>> > queries;
vector<peep> pbs;
int ans[100100];
int Q;
int d[100100];

void dfs(int i, int p, int de){
    pre[i] = cont;
    parent[i][0] = p;
    d[i] = de;
    cont++;

    for(int j : adjlst[i]){
        if(j == p) continue;
        dfs(j,i,de+1);
    }

    post[i] = cont - 1;
}

bool comparep(const peep &a, const peep &b){
    return a.m < b.m;
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a,b);

    for(int i = 25; i >= 0; i--){
        if(parent[a][i] != -1 && d[parent[a][i]] >= d[b]){
            a = parent[a][i];
        }
    }

    if(a == b) return a;

    for(int i = 25; i >= 0; i--){
        if(parent[a][i] != parent[b][i]){
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&M);
    scanf(" %d",&Q);

    edge.push_back({0,0});

    for(int i = 0; i < N - 1; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);

        adjlst[u].push_back(v);
        adjlst[v].push_back(u);
        edge.push_back({u,v});
    }

    dfs(1,-1,0);

    for(int i = 1; i <= N; i++){
        for(int j = 1; j < 30; j++){
            parent[i][j] = -1;
        }
    }

    for(int j = 1; j <= 25; j++){
        for(int i = 1; i <= N; i++){
            if(parent[i][j - 1] != -1){
                parent[i][j] = parent[ parent[i][j - 1] ][j-1];
            }
        }
    }

    poot = new node(0,N-1);

    for(int i = 0; i < M; i++){
        scanf(" %d",&p);
        scanf(" %d",&c);

        update.push_back({c,p});

        int u = edge[p].first;
        int v = edge[p].second;
        if(u == parent[v][0]) u = v;

        poot -> update(pre[u],post[u],1);
    }


    sort(update.begin(),update.end());

    for(int i = 0; i < Q; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);
        scanf(" %lld",&g);
        scanf(" %lld",&s);

        queries.push_back({{u,v},{g,s}});
        pbs.push_back({0,M-1,(M)/2, i});
    }

    sort(pbs.begin(),pbs.end(),comparep);

    while(!pbs.empty()){
        vector<peep> process = pbs;
        pbs.clear();

        int it = 0;
        root = new node(0,N - 1);
        ront = new node(0,N - 1);

        for(int i = 0; i < process.size(); i++){
            while(it != M && it <= process[i].m){
                int u = edge[update[it].second].first;
                int p = edge[update[it].second].second;
                if(u == parent[p][0]) swap(u,p);
                root -> update(pre[u],post[u],update[it].first);
                ront -> update(pre[u],post[u],1);
                it++;
            }

            int j = process[i].i;

            int u = queries[j].first.first;
            int v = queries[j].first.second;
            int c = lca(u,v);

            if(process[i].s == process[i].e){

                ans[j] = queries[j].second.first + (ront -> query(pre[u]) + ront -> query(pre[v]) - ront -> query(pre[c]) * 2 ) -
                         (poot -> query(pre[u]) + poot -> query(pre[v]) - poot -> query(pre[c]) * 2  );
            }
            else{
                if( root -> query(pre[u]) + root -> query(pre[v]) - root -> query(pre[c]) * 2 > queries[j].second.second ){
                    pbs.push_back({process[i].s,process[i].m - 1, (process[i].s + process[i].m)/2, process[i].i });
                }
                else{
                    pbs.push_back({process[i].m, process[i].e, (process[i].e + process[i].m + 1)/2, process[i].i });
                }
            }
        }

        if(!pbs.empty()){
            sort(pbs.begin(),pbs.end(), comparep);
        }
    }

    for(int i = 0; i < Q; i++){
        if(ans[i] >= 0) printf("%d\n",ans[i]);
        else printf("-1\n");
    }

}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:183:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<peep>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for(int i = 0; i < process.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~
currencies.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
currencies.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
currencies.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
currencies.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:148:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         scanf(" %d",&p);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf(" %d",&c);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
currencies.cpp:166:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         scanf(" %lld",&g);
      |         ~~~~~^~~~~~~~~~~~
currencies.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf(" %lld",&s);
      |         ~~~~~^~~~~~~~~~~~
currencies.cpp: In member function 'long long int node::query(int)':
currencies.cpp:44:5: warning: control reaches end of non-void function [-Wreturn-type]
   44 |     }
      |     ^

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