oj.uz

Submission #782304

# Submission time Handle Problem Language Result Execution time Memory
782304 2023-07-13T19:12:34 Z AmirElarbi Two Currencies (JOI23_currencies) C++14
28 / 100
 270 ms 32256 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace __gnu_pbds;
using namespace std;
const int nax = 1e5+5;
const int kax = 25+5;
const int MOD = 1e9+7;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int cnt = 0, cur = 0, tin[nax], tout[nax], up[nax][kax];
vii adj[nax];
ll dep[nax], w[nax];
void dfs(int u, int p){
    tin[u] = cur++;
    up[u][0] = p;
    for(int i = 1; i < kax; i++)
        up[u][i] = up[up[u][i-1]][i-1];
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        dep[x.fi] = dep[u]+w[x.se];
        dfs(x.fi,u);
    }
    tout[u] = cur++;
}
bool is_anc(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int i = kax-1; i >= 0; i--)
        if(!is_anc(up[u][i], v)) u = up[u][i];
    return up[u][0];
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    for (int i = 0; i < n-1; ++i)
    {
        int a,b;
        cin >> a >> b;
        a--,b--;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    for (int i = 0; i < m; ++i)
    {
        int p;
        ll c;
        cin >> p >> c;
        p--;
        cnt = c;
        w[p] += c;
    }
    dfs(0,0);
    //cout << up[6][0] << endl;
    while(q--){
        int s,t,x;
        ll y;
        cin >> s >> t >> x >> y;
        s--,t--;
        int l = lca(s,t);
        ll sm = dep[s]+dep[t]-2*dep[l];
        ll gld = sm/cnt - y/cnt;
        //cout << l << endl;
        if(gld <= 0) cout << x << endl;
        else if(gld <= x) cout << x-gld << endl;
        else cout << -1 << endl; 
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 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 2644 KB Output is correct
2 Correct 5 ms 3076 KB Output is correct
3 Correct 5 ms 3028 KB Output is correct
4 Correct 7 ms 3028 KB Output is correct
5 Correct 182 ms 25092 KB Output is correct
6 Correct 208 ms 19792 KB Output is correct
7 Correct 205 ms 22300 KB Output is correct
8 Correct 172 ms 22280 KB Output is correct
9 Correct 165 ms 22120 KB Output is correct
10 Correct 236 ms 25848 KB Output is correct
11 Correct 236 ms 25956 KB Output is correct
12 Correct 232 ms 25848 KB Output is correct
13 Correct 225 ms 25836 KB Output is correct
14 Correct 230 ms 25860 KB Output is correct
15 Correct 244 ms 31928 KB Output is correct
16 Correct 237 ms 32256 KB Output is correct
17 Correct 270 ms 31496 KB Output is correct
18 Correct 248 ms 25824 KB Output is correct
19 Correct 270 ms 25724 KB Output is correct
20 Correct 261 ms 25868 KB Output is correct
21 Correct 210 ms 25432 KB Output is correct
22 Correct 213 ms 25660 KB Output is correct
23 Correct 210 ms 25608 KB Output is correct
24 Correct 205 ms 25504 KB Output is correct
25 Correct 242 ms 26240 KB Output is correct
26 Correct 222 ms 26356 KB Output is correct
27 Correct 225 ms 26304 KB Output is correct
28 Correct 214 ms 25716 KB Output is correct
29 Correct 212 ms 25880 KB Output is correct
30 Correct 217 ms 25976 KB Output is correct
31 Correct 220 ms 25992 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 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 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -