Submission #566770

#	Time	Username	Problem	Language	Result	Execution time	Memory
566770		milisav	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1190 ms	140900 KiB

bitaro

#include<bits/stdc++.h>
#define maxn 300000
#define blk 150
using namespace std;
int n,m,q;
vector<int> a[maxn];
vector<int> b[maxn];
int city[maxn][blk];
int dist[maxn][blk];
int it[maxn];
int sz[maxn];
int c[maxn];
int ch[maxn];
bool fnd[maxn];
vector<int> topo;
priority_queue<pair<int,int> > pq;

bool ok[maxn];

void calc_small() {
    for(int iter=0;iter<n;iter++) {
        int u=topo[iter];
        pq.push({0,u});
        for(int i=0;i<b[u].size();i++) {
            it[b[u][i]]=0;
            pq.push({1+dist[b[u][i]][it[b[u][i]]],b[u][i]});
        }
        while(sz[u]<blk && !pq.empty()) {
            int d=pq.top().first;
            int nd=pq.top().second;
            pq.pop();
            int v=u;
            if(nd!=u) {
                v=city[nd][it[nd]];
                it[nd]++;
                if(it[nd]<sz[nd]) pq.push({1+dist[nd][it[nd]],nd});
            }
            if(!fnd[v]) {
                fnd[v]=true;
                dist[u][sz[u]]=d;
                city[u][sz[u]]=v;
                sz[u]++;
            }
        }
        while(!pq.empty()) pq.pop();
        for(int i=0;i<sz[u];i++) fnd[city[u][i]]=false;
    }
}

int dst[maxn];
int calc_big(int t) {
    for(int i=1;i<=n;i++) dst[i]=-1;
    for(int iter=0;iter<n;iter++) {
        int u=topo[iter];
        if(ok[u]) dst[u]=0;
        for(auto v:b[u]) {
            if(dst[v]!=-1) dst[u]=max(dst[u],dst[v]+1);
        }
        if(u==t) return dst[u];
    }
    return -1;
}

int main() {
    scanf("%d %d %d",&n,&m,&q);
    for(int i=0;i<m;i++) {
        int s,e;
        scanf("%d %d",&s,&e);
        a[s].push_back(e);
        b[e].push_back(s);
        ch[e]++;
    }

    for(int i=1;i<=n;i++) {
        ok[i]=true;
        if(ch[i]==0) topo.push_back(i);
    }
    int iter=0;
    while(iter<topo.size()) {
        int u=topo[iter];
        for(auto v:a[u]) {
            ch[v]--;
            if(ch[v]==0) topo.push_back(v);
        }
        iter++;
    }

    calc_small();

    /*for(int i=1;i<=n;i++) {
        printf("%d %d\n",i,sz[i]);
        for(int j=0;j<sz[i];j++) {
            printf("\t%d %d\n",city[i][j],dist[i][j]);
        }
    }*/

    for(int i=0;i<q;i++) {
        int t,y;
        scanf("%d %d",&t,&y);
        for(int j=0;j<y;j++) {
            scanf("%d",&c[j]);
            ok[c[j]]=false;
        }

        if(y<blk) {
            int ans=-1;
            for(int j=0;j<sz[t];j++) {
                if(ok[city[t][j]]) {
                    ans=dist[t][j];
                    break;
                }
            }
            printf("%d\n",ans);
        }
        else {
            printf("%d\n",calc_big(t));
        }

        for(int j=0;j<y;j++) {
            ok[c[j]]=true;
        }
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void calc_small()':
bitaro.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i=0;i<b[u].size();i++) {
      |                     ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(iter<topo.size()) {
      |           ~~~~^~~~~~~~~~~~
bitaro.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d",&s,&e);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |             scanf("%d",&c[j]);
      |             ~~~~~^~~~~~~~~~~~

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