oj.uz

Submission #745005

# Submission time Handle Problem Language Result Execution time Memory
745005 2023-05-19T09:51:40 Z onebit1024 Two Currencies (JOI23_currencies) C++17
10 / 100
 5000 ms 42208 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


int n,m,q;
vector<vector<int>>adj, up,tax;
vector<int>par,dist;

void comp(int u, int p){
    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);
    }
}

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 solve()
{
    cin >> n >> m >> q;
    adj.resize(n+1);
    up = vector<vector<int>>(n+1, vector<int>(21));
    vector<pair<int,int>>edges = {{0,0}};
    dist.resize(n+1);
    tax.resize(n+1);
    par.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);
    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);
    }
    while(q--){
        int u,v,g,s;
        cin >> u >> v >> g >> s;
        int l = lca(u,v);
        vector<int>res;
        while(u!=l){
            for(auto x : tax[u])res.pb(x);
            u = par[u];
        }
        while(v!=l){
            for(auto x : tax[v])res.pb(x);
            v = par[v];
        }
        sort(all(res));
        bool got = 0;
        for(int i = 0;i<res.size();++i){
            if(s>=res[i])s-=res[i];
            else{
                int need = res.size()-i;
                int val = g-need;
                if(val < 0)val = -1;
                cout << val << endl;
                got = 1;
                break;
            }
        }
        if(!got)cout << g << 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:106: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]
  106 |         for(int i = 0;i<res.size();++i){
      |                       ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 996 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 4 ms 720 KB Output is correct
8 Correct 5 ms 964 KB Output is correct
9 Correct 5 ms 1076 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 4 ms 1072 KB Output is correct
13 Correct 76 ms 1108 KB Output is correct
14 Correct 76 ms 1140 KB Output is correct
15 Correct 32 ms 1108 KB Output is correct
16 Correct 25 ms 1108 KB Output is correct
17 Correct 20 ms 980 KB Output is correct
18 Correct 32 ms 980 KB Output is correct
19 Correct 3 ms 960 KB Output is correct
20 Correct 3 ms 980 KB Output is correct
21 Correct 3 ms 980 KB Output is correct
22 Correct 4 ms 980 KB Output is correct
23 Correct 49 ms 1084 KB Output is correct
24 Correct 48 ms 1076 KB Output is correct
25 Correct 45 ms 1068 KB Output is correct
26 Correct 4 ms 984 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 4 ms 980 KB Output is correct
29 Correct 4 ms 976 KB Output is correct
30 Correct 4 ms 1024 KB Output is correct
31 Correct 4 ms 980 KB Output is correct
32 Correct 5 ms 980 KB Output is correct
33 Correct 72 ms 1120 KB Output is correct
34 Correct 74 ms 1160 KB Output is correct
35 Correct 75 ms 1176 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 964 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 6 ms 1104 KB Output is correct
5 Correct 292 ms 37916 KB Output is correct
6 Correct 313 ms 27956 KB Output is correct
7 Correct 298 ms 32320 KB Output is correct
8 Correct 240 ms 32756 KB Output is correct
9 Correct 248 ms 32688 KB Output is correct
10 Correct 355 ms 38928 KB Output is correct
11 Correct 369 ms 39064 KB Output is correct
12 Correct 363 ms 39020 KB Output is correct
13 Correct 362 ms 39000 KB Output is correct
14 Correct 362 ms 38900 KB Output is correct
15 Execution timed out 5084 ms 42208 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 78 ms 1176 KB Output is correct
3 Correct 76 ms 1228 KB Output is correct
4 Correct 72 ms 1108 KB Output is correct
5 Execution timed out 5081 ms 38952 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 996 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 4 ms 720 KB Output is correct
8 Correct 5 ms 964 KB Output is correct
9 Correct 5 ms 1076 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 4 ms 1072 KB Output is correct
13 Correct 76 ms 1108 KB Output is correct
14 Correct 76 ms 1140 KB Output is correct
15 Correct 32 ms 1108 KB Output is correct
16 Correct 25 ms 1108 KB Output is correct
17 Correct 20 ms 980 KB Output is correct
18 Correct 32 ms 980 KB Output is correct
19 Correct 3 ms 960 KB Output is correct
20 Correct 3 ms 980 KB Output is correct
21 Correct 3 ms 980 KB Output is correct
22 Correct 4 ms 980 KB Output is correct
23 Correct 49 ms 1084 KB Output is correct
24 Correct 48 ms 1076 KB Output is correct
25 Correct 45 ms 1068 KB Output is correct
26 Correct 4 ms 984 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 4 ms 980 KB Output is correct
29 Correct 4 ms 976 KB Output is correct
30 Correct 4 ms 1024 KB Output is correct
31 Correct 4 ms 980 KB Output is correct
32 Correct 5 ms 980 KB Output is correct
33 Correct 72 ms 1120 KB Output is correct
34 Correct 74 ms 1160 KB Output is correct
35 Correct 75 ms 1176 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 4 ms 964 KB Output is correct
38 Correct 4 ms 980 KB Output is correct
39 Correct 6 ms 1104 KB Output is correct
40 Correct 292 ms 37916 KB Output is correct
41 Correct 313 ms 27956 KB Output is correct
42 Correct 298 ms 32320 KB Output is correct
43 Correct 240 ms 32756 KB Output is correct
44 Correct 248 ms 32688 KB Output is correct
45 Correct 355 ms 38928 KB Output is correct
46 Correct 369 ms 39064 KB Output is correct
47 Correct 363 ms 39020 KB Output is correct
48 Correct 362 ms 39000 KB Output is correct
49 Correct 362 ms 38900 KB Output is correct
50 Execution timed out 5084 ms 42208 KB Time limit exceeded
51 Halted 0 ms 0 KB -