oj.uz

Submission #745555

# Submission time Handle Problem Language Result Execution time Memory
745555 2023-05-20T11:20:05 Z onebit1024 Two Currencies (JOI23_currencies) C++17
100 / 100
 3694 ms 657712 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 sz = 1, ptr = 0;
int mxn = 8e5+5,mxk = 22;
vector<pair<int,int>>seg(mxn*mxk),child(mxn*mxk);
void init(int n){
    while(sz < n)sz*=2;
}

pair<int,int> merge(pair<int,int>a, pair<int,int>b){
    return {a.first+b.first,a.second+b.second};
}

void upd(int curr, int prev, int lx, int rx, int i, pair<int,int>v){
    if(rx-lx==1){
        seg[curr] = v;
        return;
    }
    int m = (lx+rx)/2;
    if(i < m){
        child[curr].first = ++ptr;
        child[curr].second = child[prev].second;
        upd(child[curr].first,child[prev].first,lx,m,i,v);
    }else{
        child[curr].second = ++ptr;
        child[curr].first  = child[prev].first;
        upd(child[curr].second,child[prev].second,m,rx,i,v);
    }
    seg[curr] = merge(seg[child[curr].first], seg[child[curr].second]);
}


void upd(int curr, int prev, int i, pair<int,int>v){
    upd(curr,prev,0,sz,i,v);
}

pair<int,int>sol(int curr, int lx, int rx, int l, int r){
    if(curr==0)return {0,0};
    if(lx >= l && rx <= r)return seg[curr];
    if(rx <= l || lx >= r)return {0,0};
    int m = (lx+rx)/2;
    return merge(sol(child[curr].first,lx,m,l,r),sol(child[curr].second,m,rx,l,r));
}

pair<int,int>sol(int curr, int l, int r){
    return sol(curr,0,sz,l,r);
}
int f,n,m,q;
vector<vector<int>>tax,up;
vector<set<int>>adj;
vector<int>in,out,dist,val,par;
int t = 1;
void comp(int u, int p){
    for(int v : adj[u]){
        if(v==p)continue;
        par[v] = u;
        comp(v,u);
    }
}

void dfs(int u, int p){
    in[u] = t;
    t++;
    for(int v : adj[u]){
        if(v==p)continue;
        dist[v] = dist[u]+1;
        up[v][0] = u;
        par[v] = u;
        for(int j = 1;j<=20;++j)up[v][j] = up[up[v][j-1]][j-1];
        dfs(v,u);
    }
    out[u] = t;
    t++;
}

int lca(int u, int v){
    if(dist[v] > dist[u])swap(v,u);
    int k = dist[u]-dist[v];
    for(int j = 20;j>=0;--j){
        if(k&(1ll<<j))u = up[u][j];
    }
    if(v==u)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];
}

int go(int u, int k){
    for(int j = 0;j<=20;++j){
        if(k&(1ll<<j))u = up[u][j];
    }
    return u;
}
void solve()
{
    cin >> f >> m >> q;
    vector<pair<int,int>>edges = {{0,0}};
    n = f+m+1;
    tax.resize(n+1);
    adj.resize(n+1);
    up = vector<vector<int>>(n+1, vector<int>(21));
    dist.resize(n+1);
    in.resize(n+1);
    out.resize(n+1);
    val.resize(n+1);
    par.resize(n+1);
    for(int i = 1;i<f;++i){
        int u,v;
        cin >> u >> v;
        edges.pb({u,v});
        adj[u].insert(v);
        adj[v].insert(u);
    }
    comp(1,-1);
    for(int i = 1;i<=m;++i){
        int p,c;
        cin >> p >> c;
        int u = edges[p].first, v = edges[p].second;
        if(par[u]==v)swap(v,u);
        // par[v] = u
        tax[v].pb(c);
    }

    int p = f+1;

    for(int i = 1;i<=f;++i){
        if(tax[i].empty())continue;
        val[i] = tax[i][0];
        int prev = i;
        adj[par[i]].erase(i);
        adj[i].erase(par[i]);
        for(int j = 1;j<tax[i].size();++j){
            adj[p].insert(prev);
            adj[prev].insert(p);
            val[p] = tax[i][j];
            prev = p;
            p++;
            
        }
        adj[prev].insert(par[i]);
        adj[par[i]].insert(prev);
    }
    dfs(1,-1);

    init(2*n+1);

    segtree st;
    st.init(2*n+1);
    vector<pair<int,int>>feed={{0,0}};
    for(int i = 1;i<=n;++i){
        if(val[i]){
            st.set(in[i],1);
            st.set(out[i],-1);
            feed.pb({val[i],i});
        }
    }

    sort(all(feed));
    vector<int>root(mxn+1);

    for(int i = 1;i<feed.size();++i){
        int prev_root = root[i-1];
        int curr_root = ++ptr;
        int u = feed[i].second;
        root[i] = curr_root;
        upd(curr_root,prev_root,in[u],{feed[i].first,1});
        curr_root = ++ptr;
        prev_root = root[i];
        upd(curr_root,prev_root,out[u],{-feed[i].first,-1});
        root[i] = curr_root;
    }
    int sz = feed.size();

    while(q--){
        int u,v,g,s;
        cin >> u >> v >> g >> s;
        if(in[v] < in[u])swap(v,u);
        int l = 1, r = sz;
        int L = lca(u,v);
        
        int k1 = go(v,dist[v]-dist[L]-1), k2 = 0;
        if(u!=L)k2 = go(u,dist[u]-dist[L]-1);
        int tot = 0;
        if(u==L)tot = st.sol(in[k1],in[v]+1);
        else tot=st.sol(in[k1],in[v]+1)+st.sol(in[k2],in[u]+1);
        
        int res = -1;
        if(g>=tot)res = g-tot;
        while(l<= r){
            int m = (l+r)/2;
            pair<int,int>get;
            if(u==L){
                get = sol(root[m],in[k1],in[v]+1);
            }else get = merge(sol(root[m],in[k1],in[v]+1),sol(root[m],in[k2],in[u]+1));

            if(get.first <= s){
                int left = tot-get.second;
                res = max(res,max(-1ll,g-left));
                l = m+1;
            }else r = m-1;
        }
        cout << res << 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();
    }
}

Compilation message

currencies.cpp: In function 'void solve()':
currencies.cpp:209:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |         for(int j = 1;j<tax[i].size();++j){
      |                       ~^~~~~~~~~~~~~~
currencies.cpp:238:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |     for(int i = 1;i<feed.size();++i){
      |                   ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 557644 KB Output is correct
2 Correct 231 ms 557584 KB Output is correct
3 Correct 242 ms 557620 KB Output is correct
4 Correct 236 ms 557660 KB Output is correct
5 Correct 264 ms 559216 KB Output is correct
6 Correct 253 ms 559536 KB Output is correct
7 Correct 242 ms 558896 KB Output is correct
8 Correct 260 ms 559424 KB Output is correct
9 Correct 289 ms 559468 KB Output is correct
10 Correct 271 ms 559408 KB Output is correct
11 Correct 263 ms 559440 KB Output is correct
12 Correct 291 ms 559476 KB Output is correct
13 Correct 242 ms 559584 KB Output is correct
14 Correct 271 ms 559584 KB Output is correct
15 Correct 269 ms 559464 KB Output is correct
16 Correct 270 ms 559428 KB Output is correct
17 Correct 259 ms 559436 KB Output is correct
18 Correct 281 ms 559408 KB Output is correct
19 Correct 246 ms 559420 KB Output is correct
20 Correct 278 ms 559440 KB Output is correct
21 Correct 250 ms 559392 KB Output is correct
22 Correct 242 ms 559448 KB Output is correct
23 Correct 258 ms 559516 KB Output is correct
24 Correct 254 ms 559560 KB Output is correct
25 Correct 233 ms 559576 KB Output is correct
26 Correct 230 ms 559432 KB Output is correct
27 Correct 245 ms 559468 KB Output is correct
28 Correct 275 ms 559584 KB Output is correct
29 Correct 227 ms 559484 KB Output is correct
30 Correct 226 ms 559440 KB Output is correct
31 Correct 236 ms 559556 KB Output is correct
32 Correct 241 ms 559392 KB Output is correct
33 Correct 257 ms 559580 KB Output is correct
34 Correct 226 ms 559636 KB Output is correct
35 Correct 230 ms 559676 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 557600 KB Output is correct
2 Correct 244 ms 559336 KB Output is correct
3 Correct 234 ms 559404 KB Output is correct
4 Correct 227 ms 559480 KB Output is correct
5 Correct 2037 ms 645432 KB Output is correct
6 Correct 2750 ms 629212 KB Output is correct
7 Correct 2402 ms 628604 KB Output is correct
8 Correct 1951 ms 630056 KB Output is correct
9 Correct 1963 ms 630992 KB Output is correct
10 Correct 3079 ms 649196 KB Output is correct
11 Correct 3076 ms 649320 KB Output is correct
12 Correct 3063 ms 649200 KB Output is correct
13 Correct 3109 ms 649412 KB Output is correct
14 Correct 3367 ms 649532 KB Output is correct
15 Correct 2972 ms 657348 KB Output is correct
16 Correct 2907 ms 657712 KB Output is correct
17 Correct 2880 ms 657196 KB Output is correct
18 Correct 3676 ms 651232 KB Output is correct
19 Correct 3694 ms 651300 KB Output is correct
20 Correct 3676 ms 651400 KB Output is correct
21 Correct 1519 ms 650072 KB Output is correct
22 Correct 1462 ms 650140 KB Output is correct
23 Correct 1415 ms 650040 KB Output is correct
24 Correct 1483 ms 650004 KB Output is correct
25 Correct 2054 ms 655100 KB Output is correct
26 Correct 2037 ms 655080 KB Output is correct
27 Correct 2130 ms 655040 KB Output is correct
28 Correct 1689 ms 650552 KB Output is correct
29 Correct 1298 ms 650476 KB Output is correct
30 Correct 2019 ms 650636 KB Output is correct
31 Correct 1973 ms 650656 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 557608 KB Output is correct
2 Correct 229 ms 559616 KB Output is correct
3 Correct 227 ms 559564 KB Output is correct
4 Correct 237 ms 559520 KB Output is correct
5 Correct 1536 ms 636568 KB Output is correct
6 Correct 1518 ms 629736 KB Output is correct
7 Correct 2202 ms 630136 KB Output is correct
8 Correct 2535 ms 652136 KB Output is correct
9 Correct 2516 ms 652132 KB Output is correct
10 Correct 2520 ms 652000 KB Output is correct
11 Correct 1937 ms 654980 KB Output is correct
12 Correct 2272 ms 654952 KB Output is correct
13 Correct 2027 ms 655488 KB Output is correct
14 Correct 1331 ms 652500 KB Output is correct
15 Correct 1252 ms 652336 KB Output is correct
16 Correct 1504 ms 652540 KB Output is correct
17 Correct 1475 ms 652552 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 557644 KB Output is correct
2 Correct 231 ms 557584 KB Output is correct
3 Correct 242 ms 557620 KB Output is correct
4 Correct 236 ms 557660 KB Output is correct
5 Correct 264 ms 559216 KB Output is correct
6 Correct 253 ms 559536 KB Output is correct
7 Correct 242 ms 558896 KB Output is correct
8 Correct 260 ms 559424 KB Output is correct
9 Correct 289 ms 559468 KB Output is correct
10 Correct 271 ms 559408 KB Output is correct
11 Correct 263 ms 559440 KB Output is correct
12 Correct 291 ms 559476 KB Output is correct
13 Correct 242 ms 559584 KB Output is correct
14 Correct 271 ms 559584 KB Output is correct
15 Correct 269 ms 559464 KB Output is correct
16 Correct 270 ms 559428 KB Output is correct
17 Correct 259 ms 559436 KB Output is correct
18 Correct 281 ms 559408 KB Output is correct
19 Correct 246 ms 559420 KB Output is correct
20 Correct 278 ms 559440 KB Output is correct
21 Correct 250 ms 559392 KB Output is correct
22 Correct 242 ms 559448 KB Output is correct
23 Correct 258 ms 559516 KB Output is correct
24 Correct 254 ms 559560 KB Output is correct
25 Correct 233 ms 559576 KB Output is correct
26 Correct 230 ms 559432 KB Output is correct
27 Correct 245 ms 559468 KB Output is correct
28 Correct 275 ms 559584 KB Output is correct
29 Correct 227 ms 559484 KB Output is correct
30 Correct 226 ms 559440 KB Output is correct
31 Correct 236 ms 559556 KB Output is correct
32 Correct 241 ms 559392 KB Output is correct
33 Correct 257 ms 559580 KB Output is correct
34 Correct 226 ms 559636 KB Output is correct
35 Correct 230 ms 559676 KB Output is correct
36 Correct 222 ms 557600 KB Output is correct
37 Correct 244 ms 559336 KB Output is correct
38 Correct 234 ms 559404 KB Output is correct
39 Correct 227 ms 559480 KB Output is correct
40 Correct 2037 ms 645432 KB Output is correct
41 Correct 2750 ms 629212 KB Output is correct
42 Correct 2402 ms 628604 KB Output is correct
43 Correct 1951 ms 630056 KB Output is correct
44 Correct 1963 ms 630992 KB Output is correct
45 Correct 3079 ms 649196 KB Output is correct
46 Correct 3076 ms 649320 KB Output is correct
47 Correct 3063 ms 649200 KB Output is correct
48 Correct 3109 ms 649412 KB Output is correct
49 Correct 3367 ms 649532 KB Output is correct
50 Correct 2972 ms 657348 KB Output is correct
51 Correct 2907 ms 657712 KB Output is correct
52 Correct 2880 ms 657196 KB Output is correct
53 Correct 3676 ms 651232 KB Output is correct
54 Correct 3694 ms 651300 KB Output is correct
55 Correct 3676 ms 651400 KB Output is correct
56 Correct 1519 ms 650072 KB Output is correct
57 Correct 1462 ms 650140 KB Output is correct
58 Correct 1415 ms 650040 KB Output is correct
59 Correct 1483 ms 650004 KB Output is correct
60 Correct 2054 ms 655100 KB Output is correct
61 Correct 2037 ms 655080 KB Output is correct
62 Correct 2130 ms 655040 KB Output is correct
63 Correct 1689 ms 650552 KB Output is correct
64 Correct 1298 ms 650476 KB Output is correct
65 Correct 2019 ms 650636 KB Output is correct
66 Correct 1973 ms 650656 KB Output is correct
67 Correct 221 ms 557608 KB Output is correct
68 Correct 229 ms 559616 KB Output is correct
69 Correct 227 ms 559564 KB Output is correct
70 Correct 237 ms 559520 KB Output is correct
71 Correct 1536 ms 636568 KB Output is correct
72 Correct 1518 ms 629736 KB Output is correct
73 Correct 2202 ms 630136 KB Output is correct
74 Correct 2535 ms 652136 KB Output is correct
75 Correct 2516 ms 652132 KB Output is correct
76 Correct 2520 ms 652000 KB Output is correct
77 Correct 1937 ms 654980 KB Output is correct
78 Correct 2272 ms 654952 KB Output is correct
79 Correct 2027 ms 655488 KB Output is correct
80 Correct 1331 ms 652500 KB Output is correct
81 Correct 1252 ms 652336 KB Output is correct
82 Correct 1504 ms 652540 KB Output is correct
83 Correct 1475 ms 652552 KB Output is correct
84 Correct 2104 ms 640476 KB Output is correct
85 Correct 2322 ms 625428 KB Output is correct
86 Correct 2051 ms 610048 KB Output is correct
87 Correct 3150 ms 650684 KB Output is correct
88 Correct 3068 ms 650308 KB Output is correct
89 Correct 3044 ms 650568 KB Output is correct
90 Correct 3144 ms 650668 KB Output is correct
91 Correct 3034 ms 650688 KB Output is correct
92 Correct 3242 ms 655452 KB Output is correct
93 Correct 3033 ms 656728 KB Output is correct
94 Correct 3565 ms 651164 KB Output is correct
95 Correct 3686 ms 651124 KB Output is correct
96 Correct 3635 ms 651184 KB Output is correct
97 Correct 3637 ms 651224 KB Output is correct
98 Correct 1981 ms 650184 KB Output is correct
99 Correct 1997 ms 650308 KB Output is correct
100 Correct 1983 ms 649940 KB Output is correct
101 Correct 1902 ms 650088 KB Output is correct
102 Correct 2545 ms 655156 KB Output is correct
103 Correct 2713 ms 654972 KB Output is correct
104 Correct 2591 ms 655172 KB Output is correct
105 Correct 1724 ms 650804 KB Output is correct
106 Correct 1620 ms 650528 KB Output is correct
107 Correct 1742 ms 650568 KB Output is correct
108 Correct 1829 ms 650616 KB Output is correct