oj.uz

Submission #792805

# Submission time Handle Problem Language Result Execution time Memory
792805 2023-07-25T08:58:00 Z vjudge1 Two Currencies (JOI23_currencies) C++17
0 / 100
 2 ms 5032 KB 

// Author : حسن

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll c[N] , us[N] , a[N], b[N] , d[N] , p[N][20] , us1[N] , timer = 0;
vector<int>v[N] , vc[N];


void dfs(int n){
    int i;
    us[n] = ++timer;
    for(i = 1; i <= 20; i++)
        p[n][i] = p[p[n][i - 1]][i - 1];
    for(auto to : v[n])
        if(to != p[n][0])
            d[to] = d[n] + 1, c[to] = c[n] + c[to] , p[to][0] = n , dfs(to);
        us1[n] = ++timer;
}

bool upper(int x , int y){
    return ((us[x] <= us[y] && us1[x] >= us1[y]));
}
vector<int>ans;
ll get_lca(int x , int y){
    if(upper(x , y))
        return x;
    if(upper(y , x))
        return y;
    for(int i = 20; i >= 0; i--)
        if(p[x][i] != 0 && !upper(p[x][i] , y))
            x=  p[x][i];
    return p[x][0];
}

/*
void get(int x , int y){
    for(int i = 20; i >= 0; i--){
        if(y >= (1 << i)){
            for(auto to : vc[x]){

            }
            x = p[x][i];
            y -= (1 << i);
        }
    }
}
*/
void solve(){
    ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>m>>q;
    for(i = 1; i < n; i++){
        cin>>l>>r;
        v[l].pb(r);
        v[r].pb(l);
    }
    for(i = 1; i <= m; i++){
        cin>>x>>y;
        j = y;
        c[x]++;
    }
    dfs(1);
    while(q--){
        cin>>x>>y>>z>>f;
        k = get_lca(x , y);
        ans.clear();
        if(k == x || k == y){
            if(d[x] > d[y])
            swap(x,  y);
            m = c[x] - c[p[y][0]];
        }else
            m = c[x] - c[k] + c[y] - c[p[y][0]];
        k = m;
        x = f / y;
        k -= x;
        k = max(k ,0ll);
        if(k < z)
            cout<<-1<<"\n";
        else
            cout<<z - k<<"\n";
    }
}



int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
*/
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message

currencies.cpp: In function 'void dfs(int)':
currencies.cpp:37:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   37 |     for(auto to : v[n])
      |     ^~~
currencies.cpp:40:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |         us1[n] = ++timer;
      |         ^~~
currencies.cpp: In function 'void solve()':
currencies.cpp:72:16: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   72 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
currencies.cpp:72:32: warning: unused variable 's' [-Wunused-variable]
   72 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                ^
currencies.cpp:72:63: warning: unused variable 'mn' [-Wunused-variable]
   72 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                               ^~
currencies.cpp:72:76: warning: unused variable 'mx' [-Wunused-variable]
   72 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                            ^~
currencies.cpp: In function 'void dfs(int)':
currencies.cpp:36:17: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   36 |         p[n][i] = p[p[n][i - 1]][i - 1];
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:35:18: note: within this loop
   35 |     for(i = 1; i <= 20; i++)
      |                ~~^~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 28.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 32.0

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