Submission #483891

#	Time	Username	Problem	Language	Result	Execution time	Memory
483891		blue	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1142 ms	61424 KiB

bitaro

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 100'000;
const int rt = 50;
const int INF = 1'000'000'000;



vector<bool> occ(1+maxN, 0);

vector<pair<int, int> > distances[1+maxN];


void combine(int i, int j) //combine arrays i and j, store in i.
{
    // cerr << "combine " << i << ' ' << j << '\n';
    vector< pair<int, int> > res;
    int u = 0;
    int v = 0;
    while(1)
    {
        if(u < int(distances[i].size()) && occ[distances[i][u].second])
        {
            u++;
            continue;
        }

        if(v < int(distances[j].size()) && occ[distances[j][v].second])
        {
            v++;
            continue;
        }

        if(u >= int(distances[i].size()) && v >= int(distances[j].size()))
        {
            break;
        }
        // cerr << "o: " << distances[i].size() << ' ' << distances[j].size() << ' ' << u << ' ' << v << '\n';

        if(u >= int(distances[i].size()))
        {
            occ[distances[j][v].second] = 1;
            res.push_back(distances[j][v]);
            // cerr << "A " << distances[j][v].first << ' ' << distances[j][v].second << '\n';
            v++;
        }
        else if(v >= int(distances[j].size()))
        {
            occ[distances[i][u].second] = 1;
            res.push_back(distances[i][u]);
            // cerr << "B " << distances[i][u].first << ' ' << distances[i][u].second << '\n';
            u++;
        }
        else if(distances[i][u] > distances[j][v])
        {
            occ[distances[i][u].second] = 1;
            res.push_back(distances[i][u]);
            // cerr << "C " << distances[i][u].first << ' ' << distances[i][u].second << '\n';
            u++;
        }
        else
        {
            occ[distances[j][v].second] = 1;
            res.push_back(distances[j][v]);
            // cerr << "D " << distances[j][v].first << ' ' << distances[j][v].second << '\n';
            // cerr << v << ' ' << distances[j].size() << '\n';
            v++;
        }
    }
    // cerr << "while loop done\n";

    distances[i] = res;
    while(int(distances[i].size()) > rt)
        distances[i].pop_back();

    for(auto r:res) occ[r.second] = 0;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> edge[1+N];
    vector<int> rev_edge[1+N];

    for(int j = 1; j <= M; j++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        rev_edge[v].push_back(u);
    }


    //(dist, source), sorted decreasingly by dist
    for(int i = 1; i <= N; i++)
    {
        distances[i].push_back(make_pair(0, i));
        for(int j: rev_edge[i])
        {
            combine(i, j);
        }

        for(int u = 0; u < int(distances[i].size()); u++)
            distances[i][u].first++;
    }

    for(int i = 1; i <= N; i++)
    {
        for(int u = 0; u < int(distances[i].size()); u++)
            distances[i][u].first--;
    }






    // for(int i = 1; i <= N; i++)
    // {
    //     cerr << "\n\n" << "node " << i << ": \n";
    //     for(auto p: distances[i]) cerr << p.first << ' ' << p.second << '\n';
    // }


    for(int q = 1; q <= Q; q++)
    {
        int T, Y;
        cin >> T >> Y;

        vector<int> C(Y);
        for(int i = 0; i < Y; i++) cin >> C[i];

        if(Y >= rt)
        {
            vector<bool> excluded(1+N, 0);
            for(int c:C) excluded[c] = 1;
            vector<int> maxdist(1+N, -INF);

            for(int i = 1; i <= T; i++)
            {
                if(!excluded[i]) maxdist[i] = 0;
                for(int j: rev_edge[i]) maxdist[i] = max(maxdist[i], 1 + maxdist[j]);
            }

            if(maxdist[T] < 0) maxdist[T] = -1;
            cout << maxdist[T] << '\n';
        }
        else
        {
            for(int c:C) occ[c] = 1;
            int res = -1;

            for(pair<int, int> q: distances[T])
            {
                if(!occ[q.second])
                    res = max(res, q.first);
            }

            for(int c:C) occ[c] = 0;

            cout << res << '\n';
        }
    }
}

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