Submission #410944

#	Time	Username	Problem	Language	Result	Execution time	Memory
410944		azberjibiou	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	710 ms	92864 KiB

bitaro

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100010;
const int mxM=100;
const int mxK=100;
const ll MOD=1000000007;
const ll INF=100000000000001;
int N, M, Q;
vector <int> v[mxN], rv[mxN];
int deg[mxN];
vector <pii> num[mxN];
vector <pii> tmpv1, tmpv2, tmpv3;
int Chk[mxN];
int idx=1;
int dp[mxN];
int main()
{
    gibon
    cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)
    {
        int a, b;
        cin >> a >> b;
        v[b].push_back(a);
    }
    for(int now=1;now<=N;now++)
    {
        tmpv3.clear();
        tmpv3.push_back({now, 0});
        for(int nxt : v[now])
        {
            tmpv1.clear();
            swap(tmpv1, tmpv3);
            tmpv2.clear();  tmpv2.resize(num[nxt].size());  for(int i=0;i<num[nxt].size();i++)  tmpv2[i]=num[nxt][i];
            for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
            int cur1=0, cur2=0;
            while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
            {
                if(tmpv1[cur1].sec>tmpv2[cur2].sec)
                {
                    if(Chk[tmpv1[cur1].fir]==idx)   cur1++;
                    else
                    {
                        tmpv3.push_back(tmpv1[cur1]);
                        Chk[tmpv1[cur1++].fir]=idx;
                    }
                }
                else
                {
                    if(Chk[tmpv2[cur2].fir]==idx)   cur2++;
                    else
                    {
                        tmpv3.push_back(tmpv2[cur2]);
                        Chk[tmpv2[cur2++].fir]=idx;
                    }
                }
            }
            while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
            {
                if(Chk[tmpv1[cur1].fir]==idx)   cur1++;
                else    tmpv3.push_back(tmpv1[cur1++]);
            }
            while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
            {
                if(Chk[tmpv2[cur2].fir]==idx)   cur2++;
                else    tmpv3.push_back(tmpv2[cur2++]);
            }
            idx++;
        }
        num[now].resize(tmpv3.size());  for(int i=0;i<tmpv3.size();i++) num[now][i]=tmpv3[i];
    }
    while(Q--)
    {
        int ans=-1;
        int T, Y;
        cin >> T >> Y;
        for(int i=0;i<Y;i++)
        {
            int a;  cin >> a;
            Chk[a]=idx;
        }
        if(Y<mxK)
        {
            for(pii nxt : num[T])   if(Chk[nxt.fir]!=idx)
            {
                ans=nxt.sec;
                break;
            }
            cout << ans << '\n';
        }
        else
        {
            for(int i=1;i<=T;i++)   dp[i]=-1;
            for(int now=1;now<=T;now++)
            {
                if(Chk[now]!=idx)   dp[now]=0;
                for(int nxt : v[now])   if(dp[nxt]!=-1)
                {
                    dp[now]=max(dp[now], dp[nxt]+1);
                }
            }
            cout << dp[T] << '\n';
        }
        idx++;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:74: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             tmpv2.clear();  tmpv2.resize(num[nxt].size());  for(int i=0;i<num[nxt].size();i++)  tmpv2[i]=num[nxt][i];
      |                                                                         ~^~~~~~~~~~~~~~~~
bitaro.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
      |                         ~^~~~~~~~~~~~~
bitaro.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                   ~~~~^~~~~~~~~~~~~~
bitaro.cpp:48:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                                         ~~~~^~~~~~~~~~~~~~
bitaro.cpp:69:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:74:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:81:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         num[now].resize(tmpv3.size());  for(int i=0;i<tmpv3.size();i++) num[now][i]=tmpv3[i];
      |                                                     ~^~~~~~~~~~~~~

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