oj.uz

Submission #757292

# Submission time Handle Problem Language Result Execution time Memory
757292 2023-06-13T02:50:42 Z Ozy Two Currencies (JOI23_currencies) C++17
100 / 100
 3251 ms 171576 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define pll pair<lli,lli>

#define MAX 100000
#define lg 20
//para el vector de orden
#define val first
#define nodo second
//para los c1
#define ss first
#define cc second

struct x{
    lli hizq;
    lli hder;
    lli sum;
    lli cant;
};

lli n,m,q,a,b,cont,offset,lastkey,gld,sil,ultpos;
lli anc[MAX+2][lg+2];
vector<lli> hijos[MAX+2],plat;
vector<pll> aristas,orden;
vector<x> stree;
map<lli,lli> raiz;
pll euler[MAX+2];
pll c1,c2,c3,best;

void trip(lli pos, lli padre) {

    anc[pos][0] = padre;
    lli movil = padre;
    rep(i,1,lg) {
        anc[pos][i] = anc[movil][i-1];
        movil = anc[pos][i];
    }

    euler[pos].first = cont++;
    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        trip(h,pos);
    }
    euler[pos].second = cont;
}

void update(lli pos, lli ini , lli fin, lli des, lli v) {

    if (ini == fin && ini == des) {
        if (v > 0) {stree[pos].cant++; stree[pos].sum += v;}
        else {stree[pos].cant--; stree[pos].sum += v;}

        /*debugsl(pos);
        debugsl(ini);
        debugsl(fin);
        debug(des);
        debugsl(stree[pos].cant);
        debug(stree[pos].sum);*/

        return;
    }

    lli mitad = (ini + fin)/2;

    if (des <= mitad) {
        stree.push_back( stree[stree[pos].hizq] );
        stree[pos].hizq = cont;
        cont++;
        update(stree[pos].hizq, ini, mitad, des, v);
    }
    else {
        stree.push_back( stree[stree[pos].hder] );
        stree[pos].hder = cont;
        cont++;
        update(stree[pos].hder, mitad+1, fin, des, v);
    }

    stree[pos].sum = stree[ stree[pos].hizq ].sum + stree[ stree[pos].hder ].sum;
    stree[pos].cant = stree[ stree[pos].hizq ].cant + stree[ stree[pos].hder ].cant;

    /*debugsl(pos);
    debugsl(ini);
    debugsl(fin);
    debug(des);
    debugsl(stree[pos].cant);
    debug(stree[pos].sum);*/

}

lli lca(lli a, lli b) {
    lli movil,r = a;

    repa(i,lg,0){
        movil = anc[r][i];
        if (movil == 0) continue;
        if(euler[movil].first <= min(euler[a].first,euler[b].first) && euler[movil].second >= max(euler[a].second,euler[b].second)) continue;

        r = movil;
    }

    if(euler[r].first <= min(euler[a].first,euler[b].first) && euler[r].second >= max(euler[a].second,euler[b].second)) return r;
    else return anc[r][0];
}

pll query(lli pos, lli ini, lli fin, lli l, lli r) {

    if (ini > r || fin < l) return {0,0};
    if (l <= ini && fin <= r) return {stree[pos].sum,stree[pos].cant};

    lli mitad = (ini+fin)/2;
    pll a = query(stree[pos].hizq, ini, mitad, l, r);
    pll b = query(stree[pos].hder, mitad+1, fin, l, r);
    a.ss += b.ss;
    a.cc += b.cc;
    return a;
}

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

    cin >> n >> m >> q;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
        aristas.push_back({a,b});
    }

    cont = 1;
    trip(1,0);

    rep(i,1,m) {
        cin >> a >> b;
        if (euler[ aristas[a-1].first ].first < euler[ aristas[a-1].second ].first) a = aristas[a-1].second;
        else a = aristas[a-1].first;
        orden.push_back({b,a});
        plat.push_back(b);
    }
    sort(orden.begin(), orden.end());
    sort(plat.begin(), plat.end());
    //correcto

    //debug("LLEGUE");

    //arma el arbol persistente
    cont = 1;
    stree.push_back({0,0,0,0});
    lastkey = 0;
    for(auto act : orden) {

        //debug("nuevo");

        stree.push_back(stree[lastkey]);
        cont++;

        raiz[act.val] = cont-1;
        lastkey = cont-1;
        update(cont-1, 1,n+1, euler[act.nodo].first, act.val);

        //debug(stree[lastkey].cant);
        //debug(stree[lastkey].cant);
        //debug("resta");

        stree.push_back(stree[lastkey]);
        cont++;

        raiz[act.val] = cont-1;
        lastkey = cont-1;
        update(cont-1, 1,n+1, euler[act.nodo].second, -act.val);
    }

    //resuelve
    rep(Q, 1 , q) {
        cin >> a >> b >> gld >> sil;

        //debug("nuevo");

        lli mitad,k,ini = 1;
        lli fin = m;
        ultpos = 0;
        best = {0,0};

        while(ini <= fin) {

            mitad = (ini + fin)/2;
            k = raiz[ plat[mitad-1] ];

            c1 = query(k,1,n+1,1,euler[a].first);
            c2 = query(k,1,n+1,1,euler[b].first);
            c3 = query(k,1,n+1,1,euler[lca(a,b)].first);

            c1.first += c2.first - 2*c3.first;
            c1.second += c2.second - 2*c3.second;

            if (c1.ss <= sil) {
                ultpos = mitad;
                best = c1;
                ini = mitad+1;
            }
            else fin = mitad-1;
        }

        if (ultpos < m) {
            ultpos = plat[ultpos];
            ultpos = (sil - best.ss)/ultpos;
            best.cc += ultpos;
        }

        c1 = query(lastkey,1,n+1,1,euler[a].first);
        c2 = query(lastkey,1,n+1,1,euler[b].first);
        c3 = query(lastkey,1,n+1,1,euler[lca(a,b)].first);

        c1.first += c2.first - 2*c3.first;
        c1.second += c2.second - 2*c3.second;

        k = c1.cc - best.cc;
        gld -= k;

        if (gld >= 0) cout << gld << "\n";
        else cout << -1 << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 12 ms 5332 KB Output is correct
6 Correct 17 ms 5460 KB Output is correct
7 Correct 12 ms 4192 KB Output is correct
8 Correct 19 ms 5508 KB Output is correct
9 Correct 16 ms 5448 KB Output is correct
10 Correct 15 ms 5460 KB Output is correct
11 Correct 17 ms 5448 KB Output is correct
12 Correct 17 ms 5460 KB Output is correct
13 Correct 16 ms 5468 KB Output is correct
14 Correct 25 ms 5540 KB Output is correct
15 Correct 18 ms 5520 KB Output is correct
16 Correct 23 ms 5468 KB Output is correct
17 Correct 21 ms 5468 KB Output is correct
18 Correct 17 ms 5468 KB Output is correct
19 Correct 14 ms 5508 KB Output is correct
20 Correct 14 ms 5512 KB Output is correct
21 Correct 14 ms 5460 KB Output is correct
22 Correct 15 ms 5460 KB Output is correct
23 Correct 19 ms 5460 KB Output is correct
24 Correct 15 ms 5520 KB Output is correct
25 Correct 14 ms 5508 KB Output is correct
26 Correct 17 ms 5460 KB Output is correct
27 Correct 13 ms 5460 KB Output is correct
28 Correct 16 ms 5460 KB Output is correct
29 Correct 14 ms 5388 KB Output is correct
30 Correct 12 ms 5520 KB Output is correct
31 Correct 12 ms 5528 KB Output is correct
32 Correct 12 ms 5424 KB Output is correct
33 Correct 16 ms 5492 KB Output is correct
34 Correct 16 ms 5524 KB Output is correct
35 Correct 16 ms 5588 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 12 ms 5460 KB Output is correct
3 Correct 12 ms 5396 KB Output is correct
4 Correct 11 ms 5460 KB Output is correct
5 Correct 774 ms 165836 KB Output is correct
6 Correct 978 ms 156916 KB Output is correct
7 Correct 887 ms 160364 KB Output is correct
8 Correct 691 ms 160748 KB Output is correct
9 Correct 688 ms 161580 KB Output is correct
10 Correct 1008 ms 166320 KB Output is correct
11 Correct 995 ms 166180 KB Output is correct
12 Correct 997 ms 166192 KB Output is correct
13 Correct 995 ms 166088 KB Output is correct
14 Correct 990 ms 166092 KB Output is correct
15 Correct 1179 ms 169936 KB Output is correct
16 Correct 1228 ms 170068 KB Output is correct
17 Correct 1158 ms 169600 KB Output is correct
18 Correct 1136 ms 165704 KB Output is correct
19 Correct 1131 ms 165584 KB Output is correct
20 Correct 1147 ms 165676 KB Output is correct
21 Correct 927 ms 166232 KB Output is correct
22 Correct 925 ms 166412 KB Output is correct
23 Correct 942 ms 166272 KB Output is correct
24 Correct 916 ms 166340 KB Output is correct
25 Correct 942 ms 166360 KB Output is correct
26 Correct 923 ms 166144 KB Output is correct
27 Correct 888 ms 166176 KB Output is correct
28 Correct 833 ms 166028 KB Output is correct
29 Correct 889 ms 166140 KB Output is correct
30 Correct 873 ms 166132 KB Output is correct
31 Correct 834 ms 166120 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 17 ms 5520 KB Output is correct
3 Correct 18 ms 5588 KB Output is correct
4 Correct 17 ms 5596 KB Output is correct
5 Correct 1580 ms 168500 KB Output is correct
6 Correct 1662 ms 100000 KB Output is correct
7 Correct 2280 ms 157488 KB Output is correct
8 Correct 2875 ms 171548 KB Output is correct
9 Correct 2901 ms 171492 KB Output is correct
10 Correct 2876 ms 171576 KB Output is correct
11 Correct 2407 ms 171528 KB Output is correct
12 Correct 2486 ms 171488 KB Output is correct
13 Correct 2380 ms 171540 KB Output is correct
14 Correct 1965 ms 171400 KB Output is correct
15 Correct 1724 ms 171412 KB Output is correct
16 Correct 1981 ms 171388 KB Output is correct
17 Correct 2029 ms 171392 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 12 ms 5332 KB Output is correct
6 Correct 17 ms 5460 KB Output is correct
7 Correct 12 ms 4192 KB Output is correct
8 Correct 19 ms 5508 KB Output is correct
9 Correct 16 ms 5448 KB Output is correct
10 Correct 15 ms 5460 KB Output is correct
11 Correct 17 ms 5448 KB Output is correct
12 Correct 17 ms 5460 KB Output is correct
13 Correct 16 ms 5468 KB Output is correct
14 Correct 25 ms 5540 KB Output is correct
15 Correct 18 ms 5520 KB Output is correct
16 Correct 23 ms 5468 KB Output is correct
17 Correct 21 ms 5468 KB Output is correct
18 Correct 17 ms 5468 KB Output is correct
19 Correct 14 ms 5508 KB Output is correct
20 Correct 14 ms 5512 KB Output is correct
21 Correct 14 ms 5460 KB Output is correct
22 Correct 15 ms 5460 KB Output is correct
23 Correct 19 ms 5460 KB Output is correct
24 Correct 15 ms 5520 KB Output is correct
25 Correct 14 ms 5508 KB Output is correct
26 Correct 17 ms 5460 KB Output is correct
27 Correct 13 ms 5460 KB Output is correct
28 Correct 16 ms 5460 KB Output is correct
29 Correct 14 ms 5388 KB Output is correct
30 Correct 12 ms 5520 KB Output is correct
31 Correct 12 ms 5528 KB Output is correct
32 Correct 12 ms 5424 KB Output is correct
33 Correct 16 ms 5492 KB Output is correct
34 Correct 16 ms 5524 KB Output is correct
35 Correct 16 ms 5588 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 12 ms 5460 KB Output is correct
38 Correct 12 ms 5396 KB Output is correct
39 Correct 11 ms 5460 KB Output is correct
40 Correct 774 ms 165836 KB Output is correct
41 Correct 978 ms 156916 KB Output is correct
42 Correct 887 ms 160364 KB Output is correct
43 Correct 691 ms 160748 KB Output is correct
44 Correct 688 ms 161580 KB Output is correct
45 Correct 1008 ms 166320 KB Output is correct
46 Correct 995 ms 166180 KB Output is correct
47 Correct 997 ms 166192 KB Output is correct
48 Correct 995 ms 166088 KB Output is correct
49 Correct 990 ms 166092 KB Output is correct
50 Correct 1179 ms 169936 KB Output is correct
51 Correct 1228 ms 170068 KB Output is correct
52 Correct 1158 ms 169600 KB Output is correct
53 Correct 1136 ms 165704 KB Output is correct
54 Correct 1131 ms 165584 KB Output is correct
55 Correct 1147 ms 165676 KB Output is correct
56 Correct 927 ms 166232 KB Output is correct
57 Correct 925 ms 166412 KB Output is correct
58 Correct 942 ms 166272 KB Output is correct
59 Correct 916 ms 166340 KB Output is correct
60 Correct 942 ms 166360 KB Output is correct
61 Correct 923 ms 166144 KB Output is correct
62 Correct 888 ms 166176 KB Output is correct
63 Correct 833 ms 166028 KB Output is correct
64 Correct 889 ms 166140 KB Output is correct
65 Correct 873 ms 166132 KB Output is correct
66 Correct 834 ms 166120 KB Output is correct
67 Correct 2 ms 2644 KB Output is correct
68 Correct 17 ms 5520 KB Output is correct
69 Correct 18 ms 5588 KB Output is correct
70 Correct 17 ms 5596 KB Output is correct
71 Correct 1580 ms 168500 KB Output is correct
72 Correct 1662 ms 100000 KB Output is correct
73 Correct 2280 ms 157488 KB Output is correct
74 Correct 2875 ms 171548 KB Output is correct
75 Correct 2901 ms 171492 KB Output is correct
76 Correct 2876 ms 171576 KB Output is correct
77 Correct 2407 ms 171528 KB Output is correct
78 Correct 2486 ms 171488 KB Output is correct
79 Correct 2380 ms 171540 KB Output is correct
80 Correct 1965 ms 171400 KB Output is correct
81 Correct 1724 ms 171412 KB Output is correct
82 Correct 1981 ms 171388 KB Output is correct
83 Correct 2029 ms 171392 KB Output is correct
84 Correct 1755 ms 162816 KB Output is correct
85 Correct 1932 ms 154868 KB Output is correct
86 Correct 1836 ms 86128 KB Output is correct
87 Correct 2922 ms 167340 KB Output is correct
88 Correct 2816 ms 167340 KB Output is correct
89 Correct 2781 ms 167272 KB Output is correct
90 Correct 2768 ms 167332 KB Output is correct
91 Correct 2696 ms 167260 KB Output is correct
92 Correct 3208 ms 169632 KB Output is correct
93 Correct 3079 ms 170804 KB Output is correct
94 Correct 3251 ms 166764 KB Output is correct
95 Correct 3014 ms 166800 KB Output is correct
96 Correct 3056 ms 166828 KB Output is correct
97 Correct 3126 ms 166972 KB Output is correct
98 Correct 2609 ms 167516 KB Output is correct
99 Correct 2500 ms 167480 KB Output is correct
100 Correct 2634 ms 167448 KB Output is correct
101 Correct 2566 ms 167452 KB Output is correct
102 Correct 2473 ms 167344 KB Output is correct
103 Correct 2262 ms 167312 KB Output is correct
104 Correct 2411 ms 167352 KB Output is correct
105 Correct 1601 ms 167312 KB Output is correct
106 Correct 1364 ms 167344 KB Output is correct
107 Correct 1596 ms 167340 KB Output is correct
108 Correct 1619 ms 167332 KB Output is correct