제출 #1045219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045219		TsotneSV	Two Currencies (JOI23_currencies)	C++17	30 / 100	1731 ms	203864 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 

 #define int long long
#define fi first
#define se second
#define pb push_back
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef pair<int,int> pii;


const int lg=18,MAXN=1e5+5; 

int n,m,q,timer=1,lev[MAXN],jmp[lg][MAXN],in[MAXN],out[MAXN]; 
pii edge[MAXN],cp[MAXN]; vector<int> g[MAXN];

struct Node {
    Node *l = nullptr, *r = nullptr;
    ll sum = 0; int cnt = 0;

    Node(ll sum = 0,int f = 0) : l(nullptr),r(nullptr) {this->sum = sum,this->cnt = f;}

    Node(Node *L,Node *R) {
        this->l = L;
        this->r = R;
        sum = L->sum + R->sum;
        cnt = L->cnt + R->cnt;
    }

    Node* getL() { 
        if (!l) l = new Node();
        return l;
    }

    Node* getR() { 
        if (!r) r = new Node();
        return r;
    }
};

Node *root[MAXN];

Node* update(Node *node,int tl,int tr,int idx,ll val,int f = 0) {

    if(tl == tr) {
        return new Node(val,f);
    }else {
        int tm = (tl + tr)/2;

        if(idx <= tm) return new Node(update(node->getL(),tl,tm,idx,val,f),node->getR());
        else return new Node(node->getL(),update(node->getR(),tm+1,tr,idx,val,f));
    }

}

pair<ll,int> query(Node *node,int tl,int tr,int l,int r) {

    if(l > r) return {0,0};

    if(tl == l and tr == r) return {node->sum,node->cnt};
    else {
        int tm = (tl + tr)/2;
        auto p1 = query(node->getL(),tl,tm,l,min(r,tm)),p2 = query(node->getR(),tm+1,tr,max(l,tm+1),r);
        return {p1.fi + p2.fi,p1.se + p2.se};
    }

}

void dfs(int v,int p = 0) {

    lev[v] = lev[p] + 1; in[v] = timer++;

    jmp[0][v] = p;

    for(int i=1;i<lg;i++) jmp[i][v] = jmp[i-1][jmp[i-1][v]];

    for(int i : g[v]) {
        if(i != p) dfs(i,v);
    } out[v] = timer;

}

int lca(int u,int v) {

    if(lev[u] < lev[v]) swap(u,v);

    for(int i=lg-1;i>=0;i--) {
        if(lev[jmp[i][u]] >= lev[v]) u = jmp[i][u];
    }

    if(u == v) return u;

    for(int i=lg-1;i>=0;i--) {
        if(jmp[i][u] != jmp[i][v]) {
            u = jmp[i][u];
            v = jmp[i][v];
        }
    }

    return jmp[0][u];

}

void solve(){
    cin>>n>>m>>q; 

    for(int i=1;i<=n-1;i++) {
        int u,v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
        edge[i] = {u,v};
    }

    lev[0] = 0;

    for(int i=0;i<lg;i++) jmp[i][0] = 0;

    dfs(1); 

    root[0] = new Node();

    for(int i=1;i<=m;i++) cin>>cp[i].se>>cp[i].fi;
    
    sort(cp+1,cp+m+1); 

    for(int i=1;i<=m;i++) {
        int p = cp[i].se; ll c = cp[i].fi;
        auto [u,v] = edge[p]; if(lev[u] < lev[v]) swap(u,v);
        auto [a,b] = query(root[i-1],0,timer,in[u],in[u]);
        c += a; int f1 = b,f2 = query(root[i-1],0,timer,out[u],out[u]).se;

        root[i] = update(root[i-1],0,timer,in[u],c,f1+1);
        root[i] = update(root[i],0,timer,out[u],-c,f2-1);
    } 

    auto eval = [&](Node *r,int u,int v) {
        int LCA = lca(u,v); 
        auto p1 = query(r,0,timer,0,in[u]),p2 = query(r,0,timer,0,in[v]),p3 = query(r,0,timer,0,in[LCA]);
        return p1.fi + p2.fi - 2 * p3.fi;
    };


    while(q--) {

        int u,v,g; ll s;
        cin>>u>>v>>g>>s;

        int l = 0,r = m,tg = 0;

        while(l <= r) {
            int mid = (l + r)/2; 
            if(eval(root[mid],u,v) <= s) {
                tg = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        } 

        int a = query(root[m],0,timer,0,in[u]).se + query(root[m],0,timer,0,in[v]).se - 2 * query(root[m],0,timer,0,in[lca(u,v)]).se;
        int b = query(root[tg],0,timer,0,in[u]).se + query(root[tg],0,timer,0,in[v]).se - 2 * query(root[tg],0,timer,0,in[lca(u,v)]).se;
        a -= b; 

        cout<<max(-1ll,g - a)<<endl;
    } 


}

signed main(){
    send help
    solve();
}

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