Submission #885957

#	Time	Username	Problem	Language	Result	Execution time	Memory
885957		Zero_OP	Two Currencies (JOI23_currencies)	C++14	100 / 100	743 ms	31840 KiB

currencies

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 1e5 + 5;

int n, m, q, timerDFS, lift[20][N], h[N], s[N], t[N], uNodes[N], vNodes[N], w[N], x[N], tin[N], tout[N], L[N], R[N], res[N], lca[N];
ll y[N];
pair<int, int> a[N];
vector<int> g[N];

void dfs(int u, int e){
    tin[u] = ++timerDFS;
    //cout << u << " : " << tin[u] << '\n';

    for(int id : g[u]){
        int v = uNodes[id] ^ vNodes[id] ^ u;
        if(v != e){
            h[v] = h[u] + 1;
            lift[0][v] = u;
            for(int i = 1; i <= 17; ++i){
                lift[i][v] = lift[i - 1][lift[i - 1][v]];
            }
            dfs(v, u);
        }
    }

    tout[u] = ++timerDFS;
}

int getLCA(int u, int v){
    if(h[u] != h[v]){
        if(h[u] < h[v]) swap(u, v);
        for(int i = 17; i >= 0; --i){
            if(h[u] - (1 << i) >= h[v]){
                u = lift[i][u];
            }
        }
    }
    if(u == v) return u;

    for(int i = 17; i >= 0; --i){
        if(lift[i][u] != lift[i][v]){
            u = lift[i][u];
            v = lift[i][v];
        }
    }

    return lift[0][u];
}

struct fenwickPath{
    vector<ll> bit;
    fenwickPath(int n) : bit(2 * n + 1, 0) {}

    void update(int i, ll v){
        for(; i < (int)bit.size(); i += i & (-i)){
            bit[i] += v;
        }
    }

    ll query(int i){
        ll s = 0;
        for(; i > 0; i -= i & (-i)){
            s += bit[i];
        }
        return s;
    }

    void resetData(){
        fill(range(bit), 0LL);
    }
} goldPath(0), silverPath(0);

void add(bool type, int id, int sign){
    int u = a[id].second;

//    cout << type << ' ' << id << ' ' << sign << '\n';
    if(!type){ //silver
        silverPath.update(tin[u], a[id].first * sign);
        silverPath.update(tout[u], -a[id].first * sign);
    }
    else{ //gold
        goldPath.update(tin[u], 1 * sign);
        goldPath.update(tout[u], -1 * sign);
    }
}

ll queryPath(bool type, int i){
    if(!type) {
        return silverPath.query(tin[s[i]]) + silverPath.query(tin[t[i]]) - 2LL * silverPath.query(tin[lca[i]]);
    }
    else{
        return goldPath.query(tin[s[i]]) + goldPath.query(tin[t[i]]) - 2LL * goldPath.query(tin[lca[i]]);
    }
}

void Zero_OP(){
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(i);
        g[v].push_back(i);
        uNodes[i] = u, vNodes[i] = v;
    }

    dfs(1, 1);
    for(int i = 1; i <= m; ++i){
        int p, c;
        cin >> p >> c;
        if(tin[uNodes[p]] < tin[vNodes[p]]) p = vNodes[p];
        else p = uNodes[p];

        a[i] = {c, p};
    }

    sort(a + 1, a + 1 + m);

    for(int i = 1; i <= q; ++i){
        cin >> s[i] >> t[i] >> x[i] >> y[i];

        lca[i] = getLCA(s[i], t[i]), L[i] = 0, R[i] = m, res[i] = -1;
    }

    silverPath = fenwickPath(n), goldPath = fenwickPath(n);
    int timesTotsBS = 20; //maybe should be 17 18
    while(timesTotsBS--){

        vector<pair<int, int>> events;
        for(int i = 1; i <= q; ++i){
            if(L[i] <= R[i]){
//                cout << i << " : " << (L[i] + R[i] >> 1) << '\n';
                events.push_back({L[i] + R[i] >> 1, i});
            }
        }


        if(events.empty()) break;

        sort(range(events));

        int ptr = 1;
        for(int i = 1; i <= m; ++i){
            add(1, i, 1);
        }

        for(int i = 0; i < events.size(); ++i){
            while(ptr <= m and ptr <= events[i].first){
                add(1, ptr, -1);
                add(0, ptr, 1);
                ++ptr;
            }

            int mid = events[i].first, id = events[i].second;
            ll curSilver = queryPath(0, id), curGold = queryPath(1, id);

            if(curSilver <= y[id] and curGold <= x[id]){
                res[id] = x[id] - curGold;
                L[id] = mid + 1;

            }
            else if(curGold > x[id]){
                L[id] = mid + 1;
            }
            else R[id] = mid - 1;
        }

        silverPath.resetData();
        goldPath.resetData();
    }

    for(int i = 1; i <= q; ++i){
        cout << res[i] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("antuvu.inp", "r")){
        freopen("antuvu.inp", "r", stdin);
        freopen("antuvu.out", "w", stdout);
    }

    Zero_OP();

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Zero_OP()':
currencies.cpp:151:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |                 events.push_back({L[i] + R[i] >> 1, i});
      |                                   ~~~~~^~~~~~
currencies.cpp:165:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int i = 0; i < events.size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen("antuvu.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen("antuvu.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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