Submission #466505

#	Time	Username	Problem	Language	Result	Execution time	Memory
466505		alexander707070	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1993 ms	180324 KiB

bitaro

#include<bits/stdc++.h>
#define sq 200
using namespace std;

int n,m,q,a,b,t,w,x;
vector<int> v[100007],r[100007];
vector< pair<int,int> > best[100007];

int li[100007],tim;
vector< pair<int,int> > vv;
vector< pair<int,int> > mergev(vector< pair<int,int> > &v1,vector< pair<int,int> > &v2){
    tim++;
    int pt1=0,pt2=0;
    vv.clear();
    while(vv.size()<sq and (pt1<v1.size() or pt2<v2.size())){
        while(pt1<v1.size() and li[v1[pt1].first]==tim)pt1++;
        while(pt2<v2.size() and li[v2[pt2].first]==tim)pt2++;

        if(pt1==v1.size()){
            li[v2[pt2].first]=tim;
            vv.push_back(v2[pt2]);pt2++;
        }else if(pt2==v2.size()){
            li[v1[pt1].first]=tim;
            vv.push_back(v1[pt1]);pt1++;
        }else if(v1[pt1].second>v2[pt2].second){
            li[v1[pt1].first]=tim;
            vv.push_back(v1[pt1]);pt1++;
        }else{
            li[v2[pt2].first]=tim;
            vv.push_back(v2[pt2]);pt2++;
        }
    }
    return vv;
}
int u[100007],tmi;
int dp[100007];
int dfs(int x){
    if(r[x].size()==0 and li[x]==tim)return -100000;
    else if(r[x].size()==0)return 0;

    if(u[x]==tmi)return dp[x];
    u[x]=tmi;

    if(li[x]!=tim)dp[x]=0;
    else dp[x]=-100000;

    for(int i=0;i<r[x].size();i++){
        dp[x]=max(dp[x],dfs(r[x][i])+1);
    }

    return dp[x];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        r[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        best[i].push_back({i,0});
        for(int f=0;f<r[i].size();f++){
            best[i]=mergev(best[i],best[r[i][f]]);
        }
        for(int f=0;f<best[i].size();f++){
            best[i][f].second++;
        }
    }
    for(int i=0;i<q;i++){
        cin>>t>>w;
        tim++;
        for(int f=0;f<w;f++){
            cin>>x;li[x]=tim;
        }
        if(w<sq){
            for(int f=0;f<best[t].size();f++){
                if(li[best[t][f].first]!=tim){
                    cout<<best[t][f].second-1<<"\n";
                    break;
                }else if(f==best[t].size()-1){
                    cout<<"-1\n";
                }
            }
        }else{
            tmi++;
            if(dfs(t)>=0){
                cout<<dfs(t)<<"\n";
            }else{
                cout<<"-1\n";
            }
        }
    }


    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mergev(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:15:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while(vv.size()<sq and (pt1<v1.size() or pt2<v2.size())){
      |                             ~~~^~~~~~~~~~
bitaro.cpp:15:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while(vv.size()<sq and (pt1<v1.size() or pt2<v2.size())){
      |                                              ~~~^~~~~~~~~~
bitaro.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         while(pt1<v1.size() and li[v1[pt1].first]==tim)pt1++;
      |               ~~~^~~~~~~~~~
bitaro.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(pt2<v2.size() and li[v2[pt2].first]==tim)pt2++;
      |               ~~~^~~~~~~~~~
bitaro.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(pt1==v1.size()){
      |            ~~~^~~~~~~~~~~
bitaro.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         }else if(pt2==v2.size()){
      |                  ~~~^~~~~~~~~~~
bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int f=0;f<r[i].size();f++){
      |                     ~^~~~~~~~~~~~
bitaro.cpp:69:22: 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 |         for(int f=0;f<best[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~
bitaro.cpp:80: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]
   80 |             for(int f=0;f<best[t].size();f++){
      |                         ~^~~~~~~~~~~~~~~
bitaro.cpp:84: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]
   84 |                 }else if(f==best[t].size()-1){
      |                          ~^~~~~~~~~~~~~~~~~~

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