oj.uz

Submission #886200

# Submission time Handle Problem Language Result Execution time Memory
886200 2023-12-11T14:45:31 Z dwuy Two Currencies (JOI23_currencies) C++14
10 / 100
 1191 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{
    int sum, cnt;
    Node *l, *r;

    Node(int sum = 0, int cnt = 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};
        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;
        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 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 47 ms 57336 KB Output is correct
6 Correct 74 ms 84968 KB Output is correct
7 Correct 76 ms 75604 KB Output is correct
8 Correct 77 ms 89592 KB Output is correct
9 Correct 75 ms 89504 KB Output is correct
10 Correct 90 ms 89620 KB Output is correct
11 Correct 96 ms 89572 KB Output is correct
12 Correct 75 ms 89636 KB Output is correct
13 Correct 78 ms 89460 KB Output is correct
14 Correct 74 ms 89680 KB Output is correct
15 Correct 87 ms 90196 KB Output is correct
16 Correct 109 ms 90448 KB Output is correct
17 Correct 77 ms 90192 KB Output is correct
18 Correct 85 ms 90504 KB Output is correct
19 Correct 76 ms 89400 KB Output is correct
20 Correct 83 ms 89444 KB Output is correct
21 Correct 71 ms 89424 KB Output is correct
22 Correct 73 ms 89536 KB Output is correct
23 Correct 70 ms 89688 KB Output is correct
24 Correct 74 ms 89520 KB Output is correct
25 Correct 69 ms 89684 KB Output is correct
26 Correct 61 ms 89936 KB Output is correct
27 Correct 62 ms 89836 KB Output is correct
28 Correct 63 ms 88656 KB Output is correct
29 Correct 62 ms 89724 KB Output is correct
30 Correct 74 ms 89424 KB Output is correct
31 Correct 77 ms 89624 KB Output is correct
32 Correct 80 ms 89568 KB Output is correct
33 Correct 73 ms 89292 KB Output is correct
34 Correct 73 ms 89168 KB Output is correct
35 Correct 82 ms 89168 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 75 ms 89532 KB Output is correct
3 Correct 72 ms 89540 KB Output is correct
4 Correct 88 ms 89764 KB Output is correct
5 Runtime error 1191 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 80 ms 89288 KB Output is correct
3 Correct 74 ms 89168 KB Output is correct
4 Correct 76 ms 89176 KB Output is correct
5 Runtime error 1108 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 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 47 ms 57336 KB Output is correct
6 Correct 74 ms 84968 KB Output is correct
7 Correct 76 ms 75604 KB Output is correct
8 Correct 77 ms 89592 KB Output is correct
9 Correct 75 ms 89504 KB Output is correct
10 Correct 90 ms 89620 KB Output is correct
11 Correct 96 ms 89572 KB Output is correct
12 Correct 75 ms 89636 KB Output is correct
13 Correct 78 ms 89460 KB Output is correct
14 Correct 74 ms 89680 KB Output is correct
15 Correct 87 ms 90196 KB Output is correct
16 Correct 109 ms 90448 KB Output is correct
17 Correct 77 ms 90192 KB Output is correct
18 Correct 85 ms 90504 KB Output is correct
19 Correct 76 ms 89400 KB Output is correct
20 Correct 83 ms 89444 KB Output is correct
21 Correct 71 ms 89424 KB Output is correct
22 Correct 73 ms 89536 KB Output is correct
23 Correct 70 ms 89688 KB Output is correct
24 Correct 74 ms 89520 KB Output is correct
25 Correct 69 ms 89684 KB Output is correct
26 Correct 61 ms 89936 KB Output is correct
27 Correct 62 ms 89836 KB Output is correct
28 Correct 63 ms 88656 KB Output is correct
29 Correct 62 ms 89724 KB Output is correct
30 Correct 74 ms 89424 KB Output is correct
31 Correct 77 ms 89624 KB Output is correct
32 Correct 80 ms 89568 KB Output is correct
33 Correct 73 ms 89292 KB Output is correct
34 Correct 73 ms 89168 KB Output is correct
35 Correct 82 ms 89168 KB Output is correct
36 Correct 2 ms 10584 KB Output is correct
37 Correct 75 ms 89532 KB Output is correct
38 Correct 72 ms 89540 KB Output is correct
39 Correct 88 ms 89764 KB Output is correct
40 Runtime error 1191 ms 1048576 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -