제출 #1114325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114325		ooscode	Two Currencies (JOI23_currencies)	C++17	100 / 100	1744 ms	71040 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define debug while(1) cout << "Test\n"

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 1e18 + 10;

int n , m , q;
int seg[N << 2];
int f[N];
int l[N];
int r[N];
int mid[N];
vector<int> g[N];
vector<pair<int , int>> e;
vector<pair<int , int>> vec;
int x[N];
int y[N];
int s[N];
int en[N];
int par[N][20];
int lc[N];
vector<int> qu[N];
int st[N];
int fn[N];
int h[N];
int tim;

void dfs(int v) {
    st[v] = ++tim;
    for(int i = 1 ; i < 20 ; i++)
        par[v][i] = par[par[v][i-1]][i-1];
    for(auto u : g[v]) if(u != par[v][0]) {
        par[u][0] = v;
        h[u] = h[v] + 1;
        dfs(u);
    }
    fn[v] = tim;
}

int lca(int v , int u) {
    if(h[v] < h[u]) swap(v , u);
    int he = h[v] - h[u];
    for(int i = 0 ; i < 20 ; i++) if((1ll << i) & he) 
        v = par[v][i];
    if(v == u) return v;
    for(int i = 19 ; ~i ; i--)
        if(par[v][i] != par[u][i]) v = par[v][i] , u = par[u][i];
    return par[v][0];
}

void upd(int v , int tl , int tr , int l , int r , int x) {
    // cout << v << " " << tl << " " << tr << " " << l << " " << r << " " << x << "\n";
    if(l > r) return;

    if(tl == l && tr == r) {
        seg[v] += x;
        return;
    }

    int tm = (tl + tr) >> 1;
    int cl = v << 1 , cr = cl | 1;

    upd(cl , tl , tm , l , min(tm , r) , x);
    upd(cr , tm + 1 , tr , max(tm+1 , l) , r , x);
}

int ask(int v , int tl , int tr , int p) {
    if(tl == tr) return seg[v];
    
    int tm = (tl + tr) >> 1;
    int cl = v << 1 , cr = cl | 1;

    if(tm >= p) return ask(cl , tl , tm , p) + seg[v];
    return ask(cr , tm+1 , tr , p) + seg[v];
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1 ; i < n ; i++) {
        int v , u;
        cin >> v >> u;
        e.pb({v , u});
        g[v].pb(u);
        g[u].pb(v);
    }

    dfs(1);

    for(int i = 1 ; i <= m ; i++) {
        int id , x;
        cin >> id >> x;
        vec.pb({x , id});
    }

    sort(all(vec));

    for(int i = 1 ; i <= q ; i++) {
        cin >> s[i] >> en[i] >> x[i] >> y[i];
        lc[i] = lca(s[i] , en[i]);
        l[i] = 0;
        r[i] = m+1;
        mid[i] = (l[i] + r[i]) >> 1;
        qu[mid[i]].pb(i);
    }

    for(int i = 1 ; i <= m ; i++) {
        // cout << "kir " << i << "\n";
        int v = e[vec[i-1].S-1].F;
        int u = e[vec[i-1].S-1].S;
        if(v == par[u][0]) swap(v , u);
        upd(1 , 1 , n , st[v] , fn[v] , 1);
    }
    
    for(int i = 1 ; i <= q ; i++)
        f[i] = ask(1 , 1 , n , st[s[i]]) + ask(1 , 1 , n , st[en[i]]) - 2 * ask(1 , 1 , n , st[lc[i]]); // , cout << i << " " << f[i] << "\n";

    for(int t = 1 ; t <= 20 ; t++) {
        for(int i = 1 ; i <= 4 * n ; i++)
            seg[i] = 0;
        for(int i = 1 ; i <= m ; i++) {
            int v = e[vec[i-1].S-1].F;
            int u = e[vec[i-1].S-1].S;
            if(v == par[u][0]) swap(v , u);
            upd(1 , 1 , n , st[v] , fn[v] , vec[i-1].F);

            for(auto id : qu[i]) {
                // if(id == 1) cout << l[id] << " " << r[id] << " " << mid[id] << " oo " << ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) << "\n"; 
                if(ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) <= y[id])
                    l[id] = mid[id];
                else 
                    r[id] = mid[id];

                mid[id] = (l[id] + r[id]) >> 1; 
            }
        }
        for(int i = 1 ; i <= m ; i++)
            qu[i].clear();
        for(int i = 1 ; i <= q ; i++) 
            qu[mid[i]].pb(i);
    }

    // for(int i = 1 ; i <= q ; i++)
    //     cout << l[i] << " " << r[i] << " " << mid[i] << "\n";

    // cout << "khob kir\n";

    for(int i = 1 ; i <= 4 * n ; i++)
        seg[i] = 0;

    for(int i = 1 ; i <= m ; i++) {
        int v = e[vec[i-1].S-1].F;
        int u = e[vec[i-1].S-1].S;
        if(v == par[u][0]) swap(v , u);
        upd(1 , 1 , n , st[v] , fn[v] , 1);

        for(auto id : qu[i]) f[id] -= ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 
            2 * ask(1 , 1 , n , st[lc[id]]);
    }

    for(int i = 1 ; i <= q ; i++)
        cout << max(-1ll , x[i] - f[i]) << "\n";

    // cout << "GA\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n = 1;
    // cin >> n;
    while(n--)
        solve();
}

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