Submission #173019

#	Time	Username	Problem	Language	Result	Execution time	Memory
173019		balbit	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1746 ms	414328 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 1e5+5;

const int BS = 305;
vector<int> tome[maxn];
vector<pii> far[maxn]; // The BS-th farthest nodes from i , {a,b}: farthest distance, node number
bool seen[maxn]; // Temporary array for things in far[i]
int farth[maxn];

signed main(){
    IOS();
#ifdef BALBIT
    freopen("input.in","r",stdin);
#endif // BALBIT
    int n, m, q; cin>>n>>m>>q;
    REP(i,m) {
        int a, b; cin>>a>>b; tome[b-1].pb(a-1);
    }
    REP(i,n) {
        far[i] = {{-1,i}};
        for (int v : tome[i]) {
            vector<pii> tmp = far[i]; far[i].clear();
            int it = 0;
            for (pii x : far[v]) {
                while (it != SZ(tmp) && tmp[it].f>= x.f) {
                    if (!seen[tmp[it].s]) {
                        seen[tmp[it].s]=1;
                        far[i].push_back(tmp[it]);
                    }
                    ++it;
                }
                if (!seen[x.s]) {
                    seen[x.s]=1; far[i].push_back(x);
                }
            }
            FOR(j,it,SZ(tmp)) if (!seen[tmp[j].s]) {
                far[i].pb(tmp[j]);
                seen[tmp[j].s]=1;
            }
            for (pii x : far[i]) seen[x.s]=0;
            while (far[i].size() > BS) far[i].pop_back();
        }
        for (pii &x : far[i]) {
            ++x.f;
        }
        // Make sure to set seen back to 0
    }
    while (q--) {
        int v; cin>>v; --v;
        int Y; cin>>Y;
        vector<int> vec(Y);
        REP(i,Y) {
            cin>>vec[i]; seen[--vec[i]] = 1;
        }
        if (Y < BS) {
            bool done = 0;
            for (pii &x : far[v]) {
                if (!seen[x.s]) {
                    cout<<x.f<<endl; done = 1; break;
                }
            }
            if (!done) cout<<-1<<endl;
        }else{
            REP(i,n) {
                farth[i] = seen[i]?-n-n:0;
                for (int u : tome[i]) {
                    MX(farth[i], farth[u]+1);
                }
            }
            cout<<max(farth[v],-1)<<endl;
        }
        REP(i,Y) {
            seen[vec[i]] = 0;
        }
    }
}

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