Submission #414358

#	Time	Username	Problem	Language	Result	Execution time	Memory
414358		Runtime_error_	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1680 ms	427488 KiB

bitaro

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
const int inf = 2e5+9,sqr = 300,MX = 1e9+9;
int n,m,q,ts,vis[inf],dis[inf];
vector<int> out[inf],in[inf],blocked;
vector<pair<int,int> >furthest[inf];

vector<pair<int,int>> merge(vector<pair<int,int>> a,vector<pair<int,int>> b){
    ts++;
    vector<pair<int,int> > ret;
    int sza = a.size(),szb = b.size(),pta = 0,ptb = 0;
    for(auto &o:a)
        o.first--;
    auto add = [&](pair<int,int> x){
        x.first ++;
        ret.pb(x);
        vis[x.second] = ts;
    };
    auto validpta = [&](){
        while(pta < sza && vis[ a[pta].second ] == ts)
            pta++;
        return pta < sza;
    };
    auto validptb = [&](){
        while(ptb < szb && vis[ b[ptb].second ] == ts)
            ptb++;
        return ptb < szb;
    };
    while(validpta() && validptb() && ret.size()<sqr){
        if(a[pta].first >= b[ptb].first)
            add(a[pta]);
        else
            add(b[ptb]);
    }
    while(validpta() && ret.size() < sqr){
        add(a[pta]);
    }
    while(validptb() && ret.size() < sqr){
        add(b[ptb]);
    }
    return ret;
}

int heavy(int goal){
    int ret = -1;

    for(int i=1;i<=n;i++)
        dis[i] = -MX;
    dis[goal] = 0;
    ts++;
    for(auto o:blocked)
        vis[o] = ts;

    for(int u=goal;u>=1;u--){
        for(auto v:out[u])
            dis[u] = max(dis[u],dis[v]+1);
        if(vis[u] != ts)
            ret = max(ret,dis[u]);
    }
    return ret;
}

int light(int goal){
    //return heavy(goal);
    int ret = -1;
    ts++;
    for(auto o:blocked)
        vis[o] = ts;
    for(auto o:furthest[goal])
        if(vis[o.second] != ts)
            ret = max(ret,o.first);
    return ret;
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        out[a].pb(b);
        in[b].pb(a);
    }
    for(int u=1;u<=n;u++){
        furthest[u].pb(mp(0,u));
        for(auto v:in[u])
            furthest[u] = merge(furthest[u],furthest[v]);
    }
    while(q--){
        blocked.clear();
        int u,cnt,tmp;
        scanf("%d%d",&u,&cnt);
        for(int i=0;i<cnt;i++)
            scanf("%d",&tmp),blocked.pb(tmp);
        if(cnt >= sqr)
            printf("%d\n",heavy(u));
        else
            printf("%d\n",light(u));
    }
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
5 2 2 3
*/

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d%d",&u,&cnt);
      |         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%d",&tmp),blocked.pb(tmp);
      |             ~~~~~^~~~~~~~~~~

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