oj.uz

Submission #886202

# Submission time Handle Problem Language Result Execution time Memory
886202 2023-12-11T14:53:03 Z dwuy Two Currencies (JOI23_currencies) C++14
10 / 100
 2661 ms 1048576 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

pii operator + (const pii a, const pii b){ return {a.fi + b.fi, a.se + b.se}; }

struct Node{
    bool f;
    int sum, cnt;
    Node *l, *r;

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

    Node(Node *other){
        this->cnt = other->cnt;
        this->sum = other->sum;
        this->l = other->l;
        this->r = other->r;
    }
};

struct persistent_SMT{
    int n, m;
    vector<Node*> root;

    persistent_SMT(int n=0, int m=0){
        this->n = n;
        this->m = m;
        this->root.assign(m+5, NULL);
        root[0] = new Node();
    }

    void down(Node *cur){
        if(cur->sum == 0 && cur->cnt) return;
        if(cur->l){
            cur->l->sum += cur->sum;
            cur->l->cnt += cur->cnt;
        }
        if(cur->r){
            cur->r->sum += cur->sum;
            cur->r->cnt += cur->cnt;
        }
        cur->sum = 0;
        cur->cnt = 0;
    }

    void update(Node *cur, int l, int r, const int &u, const int &v, const int &val){
        if(l>v || r<u) return;
        if(l>=u && r<=v){
            cur->sum += val;
            cur->cnt++;
            return;
        }
        cur->l = cur->l? new Node(cur->l) : new Node();
        cur->r = cur->r? new Node(cur->r) : new Node();
        down(cur);
        int mid = (l+r)>>1;
        update(cur->l, l, mid, u, v, val);
        update(cur->r, mid+1, r, u, v, val);
    }

    void update(int u, int v, int val, int id){
        root[id] = new Node(root[id-1]);
        update(root[id], 1, n, u, v, val);
    }

    pii get(Node *cur, int l, int r, const int &pos){
        if(l == r) return {cur->sum, cur->cnt};
        if (cur->l == NULL) cur->l = new Node();
        else if(!cur->l->f) cur->l = new Node(cur->l);
        if(cur->r==NULL) cur->r = new Node();
        else if(!cur->r->f) cur->r = new Node(cur->r);
        cur->l->f = cur->r->f = 1;
        down(cur);
        int mid = (l+r)>>1;
        if(pos<=mid) return get(cur->l, l, mid, pos);
        return get(cur->r, mid+1, r, pos);
    }

    pii get(int pos, int id){
        return get(root[id], 1, n, pos);
    }
};

const int MX = 200005;
int n, m, q;
pii edges[MX];
pii weight[MX];
vector<int> G[MX];

void nhap(){
    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1; i<=m; i++){
        int p, c;
        cin >> p >> c;
        weight[i] = {c, p};
    }
}

int dfsID = 0;
int h[MX];
int p[MX][17];
int num[MX];
int clo[MX];

void dfs(int u){
    num[u] = ++dfsID;
    h[u] = h[p[u][0]] + 1;
    for(int v: G[u]){
        if(v == p[u][0]) continue;
        p[v][0] = u;
        dfs(v);
    }
    clo[u] = dfsID;
}

int LCA(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    for(int i=16; i>=0; i--) if(h[p[v][i]] >= h[u]) v = p[v][i];
    if(u == v) return u;
    for(int i=16; i>=0; i--) if(p[u][i] != p[v][i]){
        u = p[u][i];
        v = p[v][i];
    }
    return p[u][0];
}

void solve(){
    dfs(1);
    for(int j=1; j<=16; j++){
        for(int i=1; i<=n; i++){
            p[i][j] = p[p[i][j-1]][j-1];
        }
    }
    persistent_SMT smt(n, m);
    sort(weight+1, weight+1+m);
    for(int i=1; i<=m; i++){
        int u, v, c = weight[i].fi;
        tie(u, v) = edges[weight[i].se];
        if(h[u] < h[v]) swap(u, v);
        smt.update(num[u], clo[u], c, i);
    }
    for(int i=1; i<=q; i++){
        int u, v, g, s;
        cin >> u >> v >> g >> s;
        int p = LCA(u, v);
        pii fp = smt.get(num[p], m);
        pii fu = smt.get(num[u], m);
        pii fv = smt.get(num[v], m);
        int allG = fu.se + fv.se - fp.se*2;
        int res = g+1;
        for(int lo=0, hi=m; lo<=hi;){
            int mid = (lo+hi)>>1;
            pii fp = smt.get(num[p], mid);
            pii fu = smt.get(num[u], mid);
            pii fv = smt.get(num[v], mid);
            int numG = allG - (fu.se + fv.se - fp.se*2);
            int numS = fu.fi + fv.fi - fp.fi*2;
            if(numG > g) lo = mid + 1;
            else if(numS > s) hi = mid - 1;
            else res = numG, lo = mid + 1;
        }
        cout << g - res <<  endl;
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

/**

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

**/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 17 ms 24412 KB Output is correct
6 Correct 30 ms 27564 KB Output is correct
7 Correct 18 ms 22108 KB Output is correct
8 Correct 28 ms 31832 KB Output is correct
9 Correct 26 ms 31316 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 26 ms 31836 KB Output is correct
12 Correct 31 ms 31828 KB Output is correct
13 Correct 28 ms 33108 KB Output is correct
14 Correct 28 ms 33936 KB Output is correct
15 Correct 30 ms 34652 KB Output is correct
16 Correct 30 ms 35412 KB Output is correct
17 Correct 30 ms 35408 KB Output is correct
18 Correct 31 ms 35300 KB Output is correct
19 Correct 31 ms 29788 KB Output is correct
20 Correct 25 ms 29532 KB Output is correct
21 Correct 23 ms 29776 KB Output is correct
22 Correct 24 ms 29788 KB Output is correct
23 Correct 21 ms 26460 KB Output is correct
24 Correct 21 ms 27476 KB Output is correct
25 Correct 25 ms 27228 KB Output is correct
26 Correct 10 ms 15704 KB Output is correct
27 Correct 10 ms 15448 KB Output is correct
28 Correct 12 ms 18780 KB Output is correct
29 Correct 12 ms 18528 KB Output is correct
30 Correct 28 ms 31108 KB Output is correct
31 Correct 27 ms 30812 KB Output is correct
32 Correct 26 ms 30544 KB Output is correct
33 Correct 36 ms 32852 KB Output is correct
34 Correct 34 ms 32656 KB Output is correct
35 Correct 27 ms 32604 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 27 ms 31076 KB Output is correct
3 Correct 25 ms 30632 KB Output is correct
4 Correct 25 ms 30720 KB Output is correct
5 Runtime error 2661 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 28 ms 32860 KB Output is correct
3 Correct 27 ms 32604 KB Output is correct
4 Correct 27 ms 32596 KB Output is correct
5 Runtime error 2232 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 17 ms 24412 KB Output is correct
6 Correct 30 ms 27564 KB Output is correct
7 Correct 18 ms 22108 KB Output is correct
8 Correct 28 ms 31832 KB Output is correct
9 Correct 26 ms 31316 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 26 ms 31836 KB Output is correct
12 Correct 31 ms 31828 KB Output is correct
13 Correct 28 ms 33108 KB Output is correct
14 Correct 28 ms 33936 KB Output is correct
15 Correct 30 ms 34652 KB Output is correct
16 Correct 30 ms 35412 KB Output is correct
17 Correct 30 ms 35408 KB Output is correct
18 Correct 31 ms 35300 KB Output is correct
19 Correct 31 ms 29788 KB Output is correct
20 Correct 25 ms 29532 KB Output is correct
21 Correct 23 ms 29776 KB Output is correct
22 Correct 24 ms 29788 KB Output is correct
23 Correct 21 ms 26460 KB Output is correct
24 Correct 21 ms 27476 KB Output is correct
25 Correct 25 ms 27228 KB Output is correct
26 Correct 10 ms 15704 KB Output is correct
27 Correct 10 ms 15448 KB Output is correct
28 Correct 12 ms 18780 KB Output is correct
29 Correct 12 ms 18528 KB Output is correct
30 Correct 28 ms 31108 KB Output is correct
31 Correct 27 ms 30812 KB Output is correct
32 Correct 26 ms 30544 KB Output is correct
33 Correct 36 ms 32852 KB Output is correct
34 Correct 34 ms 32656 KB Output is correct
35 Correct 27 ms 32604 KB Output is correct
36 Correct 2 ms 10588 KB Output is correct
37 Correct 27 ms 31076 KB Output is correct
38 Correct 25 ms 30632 KB Output is correct
39 Correct 25 ms 30720 KB Output is correct
40 Runtime error 2661 ms 1048576 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -