제출 #1247282

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

currencies

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m, q;

long long a[maxn], b[maxn], is[maxn], s[maxn];
vector < pair < long long, long long > > g[maxn];

vector < int > on[maxn], upsie[maxn];
long long dep[maxn], par[maxn];
long long dp[maxn];
long long silverset;
void dfs0(long long beg, long long from, long long above)
{
    dp[beg] = above;
    dep[beg] = dep[from] + 1;
    par[beg] = from;
    for (auto &[nb, i]: g[beg])
    {
        if(nb == from)continue;
        dfs0(nb, beg, above + is[i]);
    }
}
void read()
{
    cin >> n >> m >> q;
    for (long long i = 1; i < n; ++ i)
    {
        cin >> a[i] >> b[i];
        g[a[i]].pb(make_pair(b[i], i));
        g[b[i]].pb(make_pair(a[i], i));
    }
    for (long long i = 1; i <= m; ++ i)
    {
        long long road, silver;
        cin >> road >> silver;

        on[road].pb(silver);
        s[road] = silver;
        silverset = silver;
        is[road] ++;
    }
    dfs0(1, 0, 0);
    for (int i = 1; i < n; ++ i)
    {
        int da = dep[a[i]], db = dep[b[i]];
        int real = a[i];
        if(da < db)real = b[i];
        for (auto silvi: on[i])
        {
            upsie[real].pb(silvi);
        }
    }
}
long long jump[maxn][20];

long long moveup(long long v, long long x)
{
    for (long long i = 0; i < 20; ++ i)
    {
        if((1 << i) & x)
        {
            v = jump[v][i];
        }
    }
    return v;
}
long long find_lca(long long u, long long v)
{
    long long du = dep[u], dv = dep[v];
    if(du > dv)swap(u, v);
    v = moveup(v, abs(du - dv));
    if(u == v)return u;
    for (long long i = 19; i >= 0; -- i)
    {
        if(jump[u][i] != jump[v][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return par[u];
}

int main()
{
    speed();

    read();

    for (long long i = 1; i <= n; ++ i)
        jump[i][0] = par[i];
    for (long long j = 1; j <  20; ++ j)
    {
        for (long long i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    }


    while(q --)
    {
        long long si, ti, xi, yi;
        cin >> si >> ti >> xi >> yi;
        long long lca = find_lca(si, ti);

        int v = si;
        vector < int > u;
        while(v != lca)
        {
            for (auto x: upsie[v])
            {
                u.pb(x);
            }
            v = par[v];
        }
        v = ti;
        while(v != lca)
        {
             for (auto x: upsie[v])
            {
                u.pb(x);
            }
            v = par[v];
        }
        sort(u.begin(), u.end());
        long long sum = 0, cnt = u.size();
        for (auto x: u)
        {
            if(sum + x <= yi)
            {
                sum += x;
                cnt --;
            }
        }
        if(cnt > xi)cout << -1 << endl;
        else cout << xi - cnt << endl;
        /* subtask 2

        long long tot = dp[si] + dp[ti] - 2*dp[lca];
        if(tot * silverset <= yi)cout << xi << endl;
        else
        {
            long long good = yi / silverset;
            if(xi >= tot - good)
            {
                cout << xi - (tot - good) << endl;
            }
            else cout << -1 << endl;
        }*/
    }
    return 0;
}

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