oj.uz

Submission #749388

# Submission time Handle Problem Language Result Execution time Memory
749388 2023-05-27T21:15:29 Z Ozy Two Currencies (JOI23_currencies) C++17
28 / 100
 234 ms 39940 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#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 pll pair<lli,lli>

#define MAX 100000
//para los hijos
#define des first
#define w second

lli n,m,q,silver,x,y,k,cont,a,b;
pair<pll, lli> aristas[MAX+2];
vector<pll> hijos[MAX+2];
lli dis[MAX+2],anc[22][MAX+2];
pll rango[MAX+2];

void dfs(lli pos,lli padre, lli s) {

    dis[pos] = dis[padre]+s;

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

    rango[pos].first = cont++;
    for(auto h : hijos[pos]) {
        if (h.des == padre) continue;
        dfs(h.des,pos,h.w);
    }
    rango[pos].second = cont++;

}

lli lca(lli a, lli b) {

    if (rango[a].first > rango[b].first) swap(a,b);

    if (rango[a].second > rango[b].second) return a;

    lli x;
    repa(i,20,0) {
        x = anc[i][a];
        if (x == 0) continue;

        if (rango[x].first < rango[a].first && rango[x].second > rango[b].second) continue;
        a = anc[i][a];
    }
    a = anc[0][a];
    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;
        aristas[i] = {{a,b},0};
    }
    rep(i,1,m) {
        cin >> a >> b;
        silver = b;
        aristas[a].second++;
    }
    rep(i,1,n-1) {
        hijos[aristas[i].first.first].push_back({aristas[i].first.second,aristas[i].second});
        hijos[aristas[i].first.second].push_back({aristas[i].first.first,aristas[i].second});
    }

    //solucion
    cont = 1;
    dfs(1,0,0);

    rep(i,1,q) {
        cin >> a >> b >> x >> y;
        k = lca(a,b);

        k = dis[a]+ dis[b] - 2*dis[k];
        y /= silver;
        k -= y;

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 4 ms 3412 KB Output is correct
5 Correct 152 ms 33500 KB Output is correct
6 Correct 149 ms 25472 KB Output is correct
7 Correct 149 ms 29272 KB Output is correct
8 Correct 137 ms 29568 KB Output is correct
9 Correct 132 ms 29352 KB Output is correct
10 Correct 181 ms 34304 KB Output is correct
11 Correct 175 ms 34304 KB Output is correct
12 Correct 177 ms 34380 KB Output is correct
13 Correct 199 ms 34288 KB Output is correct
14 Correct 190 ms 34380 KB Output is correct
15 Correct 175 ms 39544 KB Output is correct
16 Correct 169 ms 39940 KB Output is correct
17 Correct 184 ms 39252 KB Output is correct
18 Correct 234 ms 34896 KB Output is correct
19 Correct 220 ms 35052 KB Output is correct
20 Correct 225 ms 35040 KB Output is correct
21 Correct 148 ms 33232 KB Output is correct
22 Correct 153 ms 33484 KB Output is correct
23 Correct 153 ms 33412 KB Output is correct
24 Correct 152 ms 33488 KB Output is correct
25 Correct 184 ms 34808 KB Output is correct
26 Correct 163 ms 34712 KB Output is correct
27 Correct 157 ms 34772 KB Output is correct
28 Correct 132 ms 34180 KB Output is correct
29 Correct 144 ms 34132 KB Output is correct
30 Correct 142 ms 34380 KB Output is correct
31 Correct 141 ms 34408 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -