Submission #111076

#	Time	Username	Problem	Language	Result	Execution time	Memory
111076		igzi	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2091 ms	397048 KiB

bitaro

#include <bits/stdc++.h>
#define D 303
#define maxN 100005
 
using namespace std;
 
vector <int> adj[maxN],u;
vector <pair<int,int>> d[maxN];
bool mar[maxN];
int n,m,q,i,j,x,y,t,ans,dp[maxN];

vector<pair<int,int>> izbaci(vector<pair<int,int>> v){
vector<pair<int,int>> u;
int i;
for(i=0;i<v.size();i++){
if(!mar[v[i].second]){u.push_back(v[i]); mar[v[i].second]=true;}
}
for(i=0;i<u.size();i++) mar[u[i].second]=false;
while(u.size()>=D) u.pop_back();
return u;
}

vector<pair<int,int>> dodaj(vector <pair<int,int>> a,vector <pair<int,int>> b){
vector<pair<int,int>> v;
int i,j;
i=j=0;
while(i<a.size() && j<b.size()){
    if(a[i].first>=b[j].first+1) {v.push_back(a[i]); i++;}
    else {v.push_back({b[j].first+1,b[j].second}); j++;}
}
while(i<a.size()){
    v.push_back(a[i]); i++;
}
while(j<b.size()){
    v.push_back({b[j].first+1,b[j].second}); j++;
}
v=izbaci(v);
return v;
}

int resi(int x){
int ans=-1,tmp;
if(!mar[x]) ans=0;
for(int i=0;i<adj[x].size();i++){
    tmp=resi(adj[x][i]);
    if(tmp!=-1) ans=max(ans,tmp+1);
}
return ans;
}
 
int main()
{
    srand(time(NULL));
    std::ios_base::sync_with_stdio(0);
    cin>>n>>m>>q;
    for(i=0;i<m;i++){
        cin>>x>>y;
        adj[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        d[i].push_back({0,i});
        for(j=0;j<adj[i].size();j++){
            d[i]=dodaj(d[i],d[adj[i][j]]);
        }
    }
    while(q--){
        cin>>t>>x;
        u.clear();
        for(i=0;i<x;i++){
            cin>>y;
            mar[y]=true;
            u.push_back(y);
        }
        if(x<D-2){
            ans=-1;
            for(i=0;i<d[t].size();i++){
                if(!mar[d[t][i].second]){
                    ans=d[t][i].first;
                    break;
                }
            }
        }
        else{
            for(i=1;i<=t;i++){
                dp[i]=-1;
                if(!mar[i]) dp[i]=0;
                for(j=0;j<adj[i].size();j++){
                    if(dp[adj[i][j]]!=-1) dp[i]=max(dp[i],dp[adj[i][j]]+1);
                }
            }
            ans=dp[t];
        }
        for(i=0;i<u.size();i++) mar[u[i]]=false;
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > izbaci(std::vector<std::pair<int, int> >)':
bitaro.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~
bitaro.cpp:18:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<u.size();i++) mar[u[i].second]=false;
         ~^~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > dodaj(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:27:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
       ~^~~~~~~~~
bitaro.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
                     ~^~~~~~~~~
bitaro.cpp:31:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size()){
       ~^~~~~~~~~
bitaro.cpp:34:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(j<b.size()){
       ~^~~~~~~~~
bitaro.cpp: In function 'int resi(int)':
bitaro.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[x].size();i++){
             ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[i].size();j++){
                 ~^~~~~~~~~~~~~~
bitaro.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(i=0;i<d[t].size();i++){
                     ~^~~~~~~~~~~~
bitaro.cpp:87:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0;j<adj[i].size();j++){
                         ~^~~~~~~~~~~~~~
bitaro.cpp:93:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<u.size();i++) mar[u[i]]=false;
                 ~^~~~~~~~~

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