Submission #466504

#	Time	Username	Problem	Language	Result	Execution time	Memory
466504		alexander707070	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2093 ms	221236 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> > mergev(vector< pair<int,int> > &v1,vector< pair<int,int> > &v2){
    tim++;
    int pt1=0,pt2=0;
    vector< pair<int,int> > v={};
    while(v.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;
            v.push_back(v2[pt2]);pt2++;
        }else if(pt2==v2.size()){
            li[v1[pt1].first]=tim;
            v.push_back(v1[pt1]);pt1++;
        }else if(v1[pt1].second>v2[pt2].second){
            li[v1[pt1].first]=tim;
            v.push_back(v1[pt1]);pt1++;
        }else{
            li[v2[pt2].first]=tim;
            v.push_back(v2[pt2]);pt2++;
        }
    }
    return v;
}
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:14: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]
   14 |     while(v.size()<sq and (pt1<v1.size() or pt2<v2.size())){
      |                            ~~~^~~~~~~~~~
bitaro.cpp:14:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while(v.size()<sq and (pt1<v1.size() or pt2<v2.size())){
      |                                             ~~~^~~~~~~~~~
bitaro.cpp:15: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]
   15 |         while(pt1<v1.size() and li[v1[pt1].first]==tim)pt1++;
      |               ~~~^~~~~~~~~~
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(pt2<v2.size() and li[v2[pt2].first]==tim)pt2++;
      |               ~~~^~~~~~~~~~
bitaro.cpp:18: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]
   18 |         if(pt1==v1.size()){
      |            ~~~^~~~~~~~~~~
bitaro.cpp:21: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]
   21 |         }else if(pt2==v2.size()){
      |                  ~~~^~~~~~~~~~~
bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int f=0;f<r[i].size();f++){
      |                     ~^~~~~~~~~~~~
bitaro.cpp:68: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]
   68 |         for(int f=0;f<best[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~
bitaro.cpp:79: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]
   79 |             for(int f=0;f<best[t].size();f++){
      |                         ~^~~~~~~~~~~~~~~
bitaro.cpp:83: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]
   83 |                 }else if(f==best[t].size()-1){
      |                          ~^~~~~~~~~~~~~~~~~~

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