Submission #566762

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

bitaro

#include<bits/stdc++.h>
#define maxn 300000
#define blk 0
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];
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();
            dist[u][sz[u]]=d;
            if(nd!=u) {
                city[u][sz[u]]=city[nd][it[nd]];
                it[nd]++;
                if(it[nd]<sz[nd]) pq.push({1+dist[nd][it[nd]],nd});
            }
            else city[u][sz[u]]=u;
            sz[u]++;
        }
        while(!pq.empty()) pq.pop();
    }
}

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=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:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=0;i<b[u].size();i++) {
      |                     ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     while(iter<topo.size()) {
      |           ~~~~^~~~~~~~~~~~
bitaro.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d %d",&s,&e);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d %d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |             scanf("%d",&c[j]);
      |             ~~~~~^~~~~~~~~~~~
bitaro.cpp: In function 'void calc_small()':
bitaro.cpp:31:26: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   31 |             dist[u][sz[u]]=d;
      |             ~~~~~~~~~~~~~^
bitaro.cpp:37:31: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   37 |             else city[u][sz[u]]=u;
      |                  ~~~~~~~~~~~~~^
bitaro.cpp:33:47: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   33 |                 city[u][sz[u]]=city[nd][it[nd]];
      |                                ~~~~~~~~~~~~~~~^
bitaro.cpp:33:30: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   33 |                 city[u][sz[u]]=city[nd][it[nd]];
      |                 ~~~~~~~~~~~~~^
bitaro.cpp:35:61: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   35 |                 if(it[nd]<sz[nd]) pq.push({1+dist[nd][it[nd]],nd});
      |                                              ~~~~~~~~~~~~~~~^
bitaro.cpp:25:49: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   25 |             pq.push({1+dist[b[u][i]][it[b[u][i]]],b[u][i]});
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~^
bitaro.cpp: In function 'int main()':
bitaro.cpp:95:32: warning: array subscript j is outside array bounds of 'int [0]' [-Warray-bounds]
   95 |                 if(ok[city[t][j]]) {
      |                       ~~~~~~~~~^
bitaro.cpp:96:34: warning: array subscript j is outside array bounds of 'int [0]' [-Warray-bounds]
   96 |                     ans=dist[t][j];
      |                         ~~~~~~~~~^

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