oj.uz

Submission #745021

# Submission time Handle Problem Language Result Execution time Memory
745021 2023-05-19T10:10:06 Z onebit1024 Two Currencies (JOI23_currencies) C++17
28 / 100
 555 ms 52996 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

const double PI=3.141592653589;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
struct segtree{
    int size =1;
    vector<int> arr;
    void init(int n){
        while(size < n)size*=2;
        arr.resize(size*2, 0);
    }
 
    void set(int i, int v, int x, int lx, int rx){
        if(rx - lx == 1){
            arr[x] = v;
            return;
        }
        int m = (lx+rx)/2;
        if(i < m){
            set(i, v, 2*x+1, lx, m);
        }else{
            set(i, v, 2*x+2, m, rx);
        }
        arr[x] = arr[2*x+1]+arr[2*x+2];
    }
 
    void set(int i, int v){
        set(i, v, 0, 0, size);
    }
 
    int sol(int l, int r, int x, int lx, int rx){
        if(lx>=r || rx<=l)return 0;
        if(lx>=l && rx<=r)return arr[x];
        int m = (lx+rx)/2;
        int right = sol(l,r,2*x+2,m,rx);
        int left = sol(l,r,2*x+1,lx,m);
        return right+left;
    }
 
    int sol(int l, int r){
        return sol(l, r, 0, 0, size);
    }
};

int n,m,q;
vector<vector<int>>adj, up,tax;
vector<int>par,dist,sub,in,chainleader,chainpos,start;
int t = 1;
void comp(int u, int p){
    in[u] = t;
    sub[u] = 1;
    t++;
    for(int v : adj[u]){
        if(v==p)continue;
        par[v] = u;
        dist[v] = dist[u]+1;
        up[v][0] = u;
        for(int j = 1;j<=20;++j)up[v][j] = up[up[v][j-1]][j-1];
        comp(v,u);
        sub[u]+=sub[v];
    }
}

int lca(int u, int v){
    if(dist[v] > dist[u])swap(v,u);
    int k = dist[u]-dist[v];
    for(int j = 0;j<=20;++j){
        if(k&(1ll<<j))u = up[u][j];
    }
    if(u==v)return u;
    for(int j = 20;j>=0;--j){
        if(up[u][j] != up[v][j])u = up[u][j], v = up[v][j];
    }
    return up[v][0];
}

void hld(int u, int p, int pos, int leader){
    chainpos[u] = pos++;
    chainleader[u] = leader;
    int heavy = -1;
    for(int v : adj[u]){
        if(v==p)continue;
        if(sub[v] >= (sub[u]+1)/2)heavy = v;
    }
    if(heavy!=-1){
        hld(heavy,u,pos,leader);
    }
    for(int v : adj[u]){
        if(v==p || v== heavy)continue;
        hld(v,u,1,v);
    }
}
segtree st;
int give(int u, int l){
    int res = 0;
    while(chainleader[u]!=chainleader[l]){
        res+=st.sol(start[chainleader[u]],start[chainleader[u]]+chainpos[u]);
        u = par[chainleader[u]];
    }
    res+=st.sol(start[chainleader[l]]+chainpos[l],start[chainleader[u]]+chainpos[u]);
    return res;
}
void solve()
{
    cin >> n >> m >> q;
    st.init(n+1);
    adj.resize(n+1);
    up = vector<vector<int>>(n+1, vector<int>(21));
    start.resize(n+1);
    vector<pair<int,int>>edges = {{0,0}};
    dist.resize(n+1);
    tax.resize(n+1);
    in.resize(n+1);
    sub.resize(n+1);
    par.resize(n+1);
    chainleader.resize(n+1);
    chainpos.resize(n+1);
    for(int i = 1;i<n;++i){
        int u,v;
        cin >> u >> v;
        edges.pb({u,v});
        adj[u].pb(v);
        adj[v].pb(u);
    }
    comp(1,-1);
    hld(1,-1,1,1);
    vector<int>sz(n+1);
    for(int i = 1;i<=n;++i)sz[chainleader[i]]++;
    int p = 1;

    vector<int>vis(n+1);
    for(int i = 1;i<=n;++i){
        if(vis[chainleader[i]])continue;
        vis[chainleader[i]] = 1;
        start[chainleader[i]] = p;
        p+=sz[chainleader[i]];
    }

    int weight = 0;
    for(int i = 1;i<=m;++i){
        int p,c;
        cin >> p >> c;
        weight=c;
        int u = edges[p].first, v = edges[p].second;
        if(par[u] == v)swap(v,u);
        // par[v] = u
        tax[v].pb(c);
    }
    vector<vector<int>>queries;
    for(int i = 1;i<=n;++i)st.set(start[chainleader[i]]+chainpos[i]-1,tax[i].size());

    while(q--){
        int u,v,g,s;
        cin >> u >> v >> g >> s;
        if(in[v] < in[u])swap(v,u);
        int l = lca(u,v);
        int res = 0;
        if(u==l)res = give(v,u);
        else res = give(u,l)+give(v,l);

        int take = s/weight;
        int left =max(0ll,res-take);
        
        int ans = g-left;
        if(ans < 0)ans = -1;
        cout << ans << endl;
    }
}   

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    

    int T=1;
    for(int i = 1;i<=T;++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 5 ms 1132 KB Output is correct
4 Correct 5 ms 1108 KB Output is correct
5 Correct 382 ms 41200 KB Output is correct
6 Correct 429 ms 28532 KB Output is correct
7 Correct 450 ms 34112 KB Output is correct
8 Correct 347 ms 35772 KB Output is correct
9 Correct 337 ms 35588 KB Output is correct
10 Correct 510 ms 41404 KB Output is correct
11 Correct 490 ms 41384 KB Output is correct
12 Correct 489 ms 41408 KB Output is correct
13 Correct 495 ms 41412 KB Output is correct
14 Correct 529 ms 41608 KB Output is correct
15 Correct 448 ms 49368 KB Output is correct
16 Correct 442 ms 52996 KB Output is correct
17 Correct 441 ms 52204 KB Output is correct
18 Correct 549 ms 46456 KB Output is correct
19 Correct 505 ms 46396 KB Output is correct
20 Correct 555 ms 46520 KB Output is correct
21 Correct 297 ms 46104 KB Output is correct
22 Correct 289 ms 46208 KB Output is correct
23 Correct 285 ms 46124 KB Output is correct
24 Correct 293 ms 46168 KB Output is correct
25 Correct 421 ms 46580 KB Output is correct
26 Correct 406 ms 46640 KB Output is correct
27 Correct 404 ms 46392 KB Output is correct
28 Correct 313 ms 46396 KB Output is correct
29 Correct 278 ms 46500 KB Output is correct
30 Correct 327 ms 46584 KB Output is correct
31 Correct 320 ms 46620 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 32.0

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