Submission #697283

#	Time	Username	Problem	Language	Result	Execution time	Memory
697283		TS_2392	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	165 ms	9804 KiB

bitaro

#include <bits/stdc++.h>

#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define epl emplace
#define eb emplace_back

#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "

#define fi first
#define se second
#define mp make_pair

#define sqr(x) (x) * (x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define lwb lower_bound
#define upb upper_bound
#define ctz __builtin_ctzll
#define pct __builtin_popcountll

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 1e5 + 3, Bz = 317;
int n, m, qsn, d[N], who[N];
bool busy[N], seen[N];
vector<int> adj[N], radj[N];
vector<pii> bestd[N];
int main(){
    SPEED;
    cin >> n >> m >> qsn;
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        adj[u].eb(v); radj[v].eb(u);
    }
    for(int i = 1; i <= n; ++i){
        vector<pii> tmp;
        tmp.eb(i, -1);
        for(int &j : radj[i]){
            int i1 = 0, i2 = 0, sz1 = tmp.size(), sz2 = bestd[j].size();
            while((i1 < sz1 || i2 < sz2) && (int)bestd[i].size() < Bz){
                pii v1 = (i1 == sz1) ? mp(-N, -N) : tmp[i1];
                pii v2 = (i2 == sz2) ? mp(-N, -N) : bestd[j][i2];
                if(v1.se > v2.se){
                    if(!seen[v1.fi]){
                        seen[v1.fi] = true;
                        bestd[i].eb(v1);
                    }
                    ++i1;
                }
                else{
                    if(!seen[v2.fi]){
                        seen[v2.fi] = true;
                        bestd[i].eb(v2);
                    }
                    ++i2;
                }
                for(pii &v : bestd[i]) seen[v.fi] = false;
            }
            swap(tmp, bestd[i]); bestd[i].clear();
        }
        swap(tmp, bestd[i]);
        for(pii &v : bestd[i]) ++v.se;
    }
    while(qsn--){
        int city, e;
        cin >> city >> e;
        for(int i = 1; i <= e; ++i){
            cin >> who[i];
            busy[who[i]] = true;
        }
        if(e >= Bz){
            fill(d + 1, d + 1 + city, -1);
            int res = -1; d[city] = 0;
            for(int i = city - 1; i >= 1; --i){
                for(int &j : adj[i]) if(d[j] > 0) maximize(d[i], d[j] + 1);
                if(!busy[i]) maximize(res, d[i]);
            }
            cout << res << '\n';
        }
        else{
            bool bad = true;
            for(pii &v : bestd[city]) if(!busy[v.fi]){
                cout << v.se << '\n';
                bad = false; break;
            }
            if(bad) cout << -1 << '\n';
        }
        for(int i = 1; i <= e; ++i) busy[who[i]] = false;
    }
    return 0;
}

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