Submission #703914

#	Time	Username	Problem	Language	Result	Execution time	Memory
703914		igzi	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	894 ms	146052 KiB

bitaro

#include <bits/stdc++.h>
#define D 103
#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>> 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++;
}
vector<pair<int,int>> u;
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;
}
 
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);
        }
        ans=-1;
        for(i=0;i<d[t].size();i++){
            if(!mar[d[t][i].second]){
                ans=d[t][i].first;
                break;
            }
        }
        if(x>=D-2 && ans==-1)
        {
            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<<"\n";
    }
    return 0;
}

Compilation message (stderr)

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:16:8: 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(i<a.size() && j<b.size()){
      |       ~^~~~~~~~~
bitaro.cpp:16: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]
   16 | while(i<a.size() && j<b.size()){
      |                     ~^~~~~~~~~
bitaro.cpp:20:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | while(i<a.size()){
      |       ~^~~~~~~~~
bitaro.cpp:23:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | while(j<b.size()){
      |       ~^~~~~~~~~
bitaro.cpp:27:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | for(i=0;i<v.size();i++){
      |         ~^~~~~~~~~
bitaro.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | for(i=0;i<u.size();i++) mar[u[i].second]=false;
      |         ~^~~~~~~~~
bitaro.cpp: In function 'int main()':
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(j=0;j<adj[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
bitaro.cpp:59: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]
   59 |         for(i=0;i<d[t].size();i++){
      |                 ~^~~~~~~~~~~~
bitaro.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for(j=0;j<adj[i].size();j++){
      |                         ~^~~~~~~~~~~~~~
bitaro.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(i=0;i<u.size();i++) mar[u[i]]=false;
      |                 ~^~~~~~~~~

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