Submission #1247232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247232		nerrrmin	Two Currencies (JOI23_currencies)	C++20	28 / 100	145 ms	38176 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];


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;
        s[road] = silver;
        silverset = silver;
        is[road] ++;
    }
    dfs0(1, 0, 0);
}
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);
        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: 0 / 10
• Subtask 2: 28 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32