제출 #410943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410943		azberjibiou	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1137 ms	92344 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;
queue <int> que;
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 i=1;i<=N;i++)
    {
        if(v[i].empty())    que.push(i);
    }
    for(int now=1;now<=N;now++)
    {
        tmpv3.clear();
        tmpv3.push_back({now, 0});
        for(int nxt : v[now])
        {
            tmpv1.clear();  tmpv1.resize(tmpv3.size());   for(int i=0;i<tmpv3.size();i++)  tmpv1[i]=tmpv3[i];
            tmpv3.clear();
            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].fir==tmpv2[cur2].fir)
                {
                    tmpv3.push_back({tmpv1[cur1].fir, max(tmpv1[cur1].sec, tmpv2[cur2].sec)});
                    cur1++; cur2++;
                }
                else if(tmpv1[cur1].sec>tmpv2[cur2].sec)
                {
                    tmpv3.push_back(tmpv1[cur1++]);
                }
                else    tmpv3.push_back(tmpv2[cur2++]);
            }
            while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
            {
                tmpv3.push_back(tmpv1[cur1++]);
            }
            while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
            {
                tmpv3.push_back(tmpv2[cur2++]);
            }
        }
        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<=N;i++)   dp[i]=-1;
            for(int now=1;now<=N;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++;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int main()':
bitaro.cpp:48:72: 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 |             tmpv1.clear();  tmpv1.resize(tmpv3.size());   for(int i=0;i<tmpv3.size();i++)  tmpv1[i]=tmpv3[i];
      |                                                                       ~^~~~~~~~~~~~~
bitaro.cpp:50: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]
   50 |             tmpv2.clear();  tmpv2.resize(num[nxt].size());  for(int i=0;i<num[nxt].size();i++)  tmpv2[i]=num[nxt][i];
      |                                                                         ~^~~~~~~~~~~~~~~~
bitaro.cpp:51: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]
   51 |             for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
      |                         ~^~~~~~~~~~~~~
bitaro.cpp:53: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]
   53 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                   ~~~~^~~~~~~~~~~~~~
bitaro.cpp:53: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]
   53 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                                         ~~~~^~~~~~~~~~~~~~
bitaro.cpp:66: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]
   66 |             while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:70: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]
   70 |             while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:75: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]
   75 |         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: 0 / 86