Submission #864987

#	Time	Username	Problem	Language	Result	Execution time	Memory
864987		BBart888	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1150 ms	254076 KiB

bitaro

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h>      
#include <stdlib.h>     
#include <time.h> 
#include <string>
#include <fstream>



using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;



const ll MOD = 1e9 + 7;
const int MAXN = 2e5 + 11;
const int K = 100;



int n, m, q;
vector<int> adj[MAXN];
vector<int> adj_rev[MAXN];
vector<pair<int,int>> verts[MAXN];
bool bad[MAXN];



bool cmp(const pair<int, int> &a, const pair<int, int>& b)
{
    return a.first > b.first;

}


void init()
{

    for (int i = 1; i <= n; i++)
    {
        verts[i].push_back({ 0,i });
        sort(verts[i].begin(), verts[i].end(),cmp);
        vector<pair<int, int>> tmp;

        for (int j = 0; j < verts[i].size(); j++)
        {
            if (j == 0 || (verts[i][j].second != verts[i][j - 1].second))
            {
                tmp.push_back(verts[i][j]);
            }
            if (tmp.size() > K+3)
                break;
        }

        verts[i] = tmp;

        for (auto u : adj[i])
        {
            for (int j = 0; j < verts[i].size(); j++)
                verts[u].push_back({ verts[i][j].first + 1,verts[i][j].second });
            
        }

    }



}



int bfs(int source)
{
    queue<int> q;
    vector<int> dist(n + 1,-1e9);
    
    int res = -1;
    dist[source] = 0;
    

    for (int i = n; i >= 0; i--)
    {
        for (auto v : adj[i])
            dist[i] = max(dist[v]+1, dist[i]);
        //cout << i << " " << dist[i] << '\n';
        if (!bad[i])
        {
            res = max(res, dist[i]);
        }
    }



    return res;
}







int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    

    //freopen("exercise.in", "r", stdin);
    //freopen("exercise.out", "w", stdout);


    cin >> n >> m >> q;

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj_rev[b].push_back(a);
        adj[a].push_back(b);
    }
    
    
    init();

    
   
    for (int i = 0; i < q; i++)
    {
        int t, y;
        cin >> t >> y;

        if (y < K)
        {
            vector<int> dels;
            for (int j = 0; j < y; j++)
            {
                int x;
                cin >> x;
                dels.push_back(x);
                bad[x] = true;
            }

            int best = -1;

            for (int j = 0; j < verts[t].size(); j++)
            {
                if (!bad[verts[t][j].second])
                    best = max(best, verts[t][j].first);
            }


            for (int j : dels)
                bad[j] = false;

            cout << best << '\n';

        }
        else
        {
            //bfs(t);
            vector<int> dels;
            for (int j = 0; j < y; j++)
            {
                int x;
                cin >> x;
                dels.push_back(x);
                bad[x] = true;
            }

            //int best = -1;

            cout << bfs(t) << '\n';

            for (int j : dels)
                bad[j] = false;
        }
        

    }










    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void init()':
bitaro.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < verts[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j = 0; j < verts[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:158:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for (int j = 0; j < verts[t].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~

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