제출 #1281869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281869		ghammazhassan	Two Currencies (JOI23_currencies)	C++20	10 / 100	355 ms	40128 KiB

currencies

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e9;
const int LOG=17;
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
vector<int>a[N];
int p[N];
int st[LOG][N];
int pm[N];
int di[N];
void makest(){
    for (int i=1;i<N;i++){
        st[0][i]=p[i];
    }
    for (int j=1;j<LOG;j++){
        for (int i=1;i<N;i++){
            st[j][i]=st[j-1][st[j-1][i]];
        }
    }
}
int up(int x,int d){
    int k=LOG-1;
    while (k>=0){
        if ((1<<k)<=d){
            d-=1<<k;
            x=st[k][x];
        }
        k--;
    }
    return x;
}
int lca(int x,int y){
    if (di[x]<di[y]){
        swap(x,y);
    }
    x=up(x,di[x]-di[y]);
    if (x==y)return x;
    int k=LOG-1;
    while (k>=0){
        if (st[k][x]!=st[k][y]){
            x=st[k][x];
            y=st[k][y];
        }
        k--;
    }
    return p[x];
}
void solve()
{       
    cin >> n >> m >> q;
    map<pair<int,int>,int>d;
    for (int i=1;i<n;i++){
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
        d[{x,y}]=i;
        d[{y,x}]=i;
    }
    vector<vector<int>>ch(n);
    for (int i=0;i<m;i++){
        cin >> x >> y;
        c=y;
        ch[x].push_back(y);
        pm[x]++;
    }
    p[1]=0;
    queue<int>o;
    vector<int>vi(n+1);
    o.push(1);
    vi[1]=1;
    while(o.size()){
        int h=o.front();
        o.pop();
        for (int i:a[h]){
            if (vi[i])continue;
            vi[i]=1;
            di[i]=di[h]+1;
            o.push(i);
            pm[i]+=pm[h];
            p[i]=h;
        }
    }
    if (n<=2000 and m<=2000 and q<=2000){
        for (int i=0;i<q;i++){
            int g,s;
            cin >> x >> y >> g >> s;
            vector<int>l;
            while (x!=y){
                if (di[x]<di[y]){
                    swap(x,y);
                }
                for (int k:ch[d[{x,p[x]}]]){
                    l.push_back(k);
                }
                x=p[x];
            }
            sort(l.begin(),l.end());
            for (int j:l){
                if (j<=s){
                    s-=j;
                }
                else{
                    g--;
                }
            }
            cout << max(-1ll,g) << endl;
        }
        return;
    }
    makest();
    for (int i=0;i<q;i++){
        int g,s;
        cin >> x >> y >> g >> s;
        g+=s/c;
        z=lca(x,y);
        cout << max(-1ll,g-(pm[x]+pm[y]-2*pm[z])) << endl;
    }
}
signed main()    
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

• Subtask 1: 10 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32