Submission #826987

#	Time	Username	Problem	Language	Result	Execution time	Memory
826987		Hanksburger	Two Currencies (JOI23_currencies)	C++17	10 / 100	5045 ms	21780 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
long long depth[100005], par[100005], ind[100005];
vector<pair<long long, long long> > adj[100005];
vector<long long> vec[100005], res;
void dfs(long long u, long long p)
{
    par[u]=p;
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i].first, w=adj[u][i].second;
        if (v==p)
            continue;
        depth[v]=depth[u]+1;
        ind[v]=w;
        dfs(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, q;
    cin >> n >> m >> q;
    for (long long i=1; i<n; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for (long long i=1; i<=m; i++)
    {
        long long x, y;
        cin >> x >> y;
        vec[x].push_back(y);
    }
    dfs(1, 1);
    for (long long i=1; i<=q; i++)
    {
        long long a, b, c, d, curA, curB, sum=0;
        cin >> a >> b >> c >> d;
        if (depth[a]<depth[b])
            swap(a, b);
        res.clear();
        curA=a, curB=b;
        for (long long j=1; j<=depth[a]-depth[b]; j++)
        {
            for (long long k=0; k<vec[ind[curA]].size(); k++)
                res.push_back(vec[ind[curA]][k]);
            curA=par[curA];
        }
        while (curA!=curB)
        {
            for (long long k=0; k<vec[ind[curA]].size(); k++)
                res.push_back(vec[ind[curA]][k]);
            curA=par[curA];
            for (long long k=0; k<vec[ind[curB]].size(); k++)
                res.push_back(vec[ind[curB]][k]);
            curB=par[curB];
        }
        sort(res.begin(), res.end());
        for (long long j=0; j<=res.size(); j++)
        {
            if (j<res.size() && sum+res[j]<=d)
                sum+=res[j];
            else
            {
                cout << max(-1LL, c-((long long)res.size()-j)) << '\n';
                break;
            }
        }
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:9:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:50:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (long long k=0; k<vec[ind[curA]].size(); k++)
      |                                 ~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:56:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for (long long k=0; k<vec[ind[curA]].size(); k++)
      |                                 ~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:59:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (long long k=0; k<vec[ind[curB]].size(); k++)
      |                                 ~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:64:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (long long j=0; j<=res.size(); j++)
      |                             ~^~~~~~~~~~~~
currencies.cpp:66:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (j<res.size() && sum+res[j]<=d)
      |                 ~^~~~~~~~~~~

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