Submission #889132

#	Time	Username	Problem	Language	Result	Execution time	Memory
889132		Yang8on	Two Currencies (JOI23_currencies)	C++14	0 / 100	3 ms	7004 KiB

currencies

#include <bits/stdc++.h>

#define Yang8on Nguyen_Dinh_Son
#define sonphamay Nguyen_Dinh_Son

#define aothtday "Two Currencies"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define endl '\n'
#define pii pair<int, ll>
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define f first
#define s second
#define maxn 100005
#define maxm
#define maxx
#define mod 1000000007
#define base 311
#define ModHas 1000000003ll
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, m, Q;
int h[maxn], cha[maxn][20];
pair<int, int> edge[maxn];
vector<int> o[maxn], store[maxn];

void dfs(int u, int par)
{
    for(int v : o[u])
    {
        if(v == par) continue;

        h[v] = h[u] + 1;
        cha[v][0] = u;

        fi(j, 1, 17)
        {
            cha[v][j] = cha[ cha[v][j - 1] ][j - 1];
        }

        dfs(v, u);
    }
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int kc = h[u] - h[v];

    fi(i, 0, 17) if( gb(kc, i) ) u = cha[u][i];

    if(u == v) return u;

    fid(i, 17, 0)
    {
        if(cha[u][i] != cha[v][i])
        {
            u = cha[u][i];
            v = cha[v][i];
        }
    }

    return cha[u][0];
}

void solve()
{
    cin >> n >> m >> Q;
    fi(i, 1, n - 1)
    {
        cin >> edge[i].f >> edge[i].s ;
        int u = edge[i].f, v = edge[i].s;
        o[u].pb(v);
        o[v].pb(u);
    }

    dfs(1, -1);

    fi(i, 1, m)
    {
        int id;
        ll val;
        cin >> id >> val;

        int u = edge[id].f, v = edge[id].s;
        if(h[v] < h[u]) swap(u, v);

        store[v].pb(val);
    }

    fi(i, 1, Q)
    {
        int u, v, Gold, Silver;
        int G = Gold, S = Silver;

        cin >> u >> v >> G >> S;

        int par = lca(u, v);
        priority_queue<ll> q;

        while(u != par)
        {
            for(ll x : store[u])
            {
                q.push(-x);
            }

            u = cha[u][0];
        }

        while(v != par)
        {
            for(ll x : store[v])
            {
                q.push(-x);
            }

            v = cha[v][0];
        }

        int notok = 0;
        while(q.size())
        {
            ll val = -q.top();
            q.pop();

            if(S < val)
            {
                if(G == 0)
                {
                    notok = 1;
                    break;
                }
                G --;
            }
            else S -= val;
        }

        if(notok) cout << -1 << '\n';
        else cout << G << '\n';
    }
}

int main()
{
    if(fopen(aothtday".inp", "r"))
    {
        freopen(aothtday".inp","r",stdin);
        freopen(aothtday".out","w",stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
//    cin >> nTest;

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

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(aothtday".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(aothtday".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:106:13: warning: 'Gold' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |         int G = Gold, S = Silver;
      |             ^
currencies.cpp:106:23: warning: 'Silver' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |         int G = Gold, S = Silver;
      |                       ^

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