Submission #1016986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016986		codefox	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1473 ms	238364 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#pragma GCC optimize("Ofast")

int N = 100;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> graph(n);
    vector<vector<pii>> best(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
    }
    vector<int> done(n, 0);
    for (int i = 0; i < n; i++)
    {
        best[i].push_back({0, i});
        sort(best[i].begin(), best[i].end(), greater<pii>());
        vector<pii> nb;
        for (pii ele:best[i])
        {
            if (done[ele.second]) continue;
            if (nb.size()==N) break;
            done[ele.second] = 1;
            nb.push_back(ele);
        }
        best[i] = nb;
        for (int ele:graph[i])
        {
            for (pii ele2:best[i]) best[ele].push_back({ele2.first+1, ele2.second});
        }
        for (pii ele:best[i]) done[ele.second] = 0;
    }

    vector<int> usable(n, 1);
    while (q--)
    {
        int x, c;
        cin >> x >> c;
        x--;
        vector<int> nused(c);
        for (int i = 0; i < c; i++)
        {
            cin >> nused[i];
            nused[i]--;
            usable[nused[i]]=0;
        }
        if (c >= N)
        {
            int mx = -1;
            vector<int> dist(n, -1e9);
            dist[x] = 0;
            for (int j = x; j >= 0; j--)
            {
                for (int ele:graph[j])
                {
                    dist[j] = max(dist[j], dist[ele]+1);
                }
                if (usable[j]) mx = max(mx, dist[j]);
            }
            cout << mx << "\n";
        }
        else
        {
            int b = 0;
            for (pii ele:best[x])
            {
                if (usable[ele.second])
                {
                    cout << ele.first << "\n";
                    b=1;
                    break;
                }
            }
            if (!b) cout << -1 << "\n";
        }
        for (int ele:nused) usable[ele] = 1;
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:33:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |             if (nb.size()==N) break;
      |                 ~~~~~~~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86