Submission #1116855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116855		Mike_Vu	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	856 ms	333452 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e5+5, B = 400;
int n, m, q;
vector<int> adj[maxn], revadj[maxn];
pii val[maxn][B+5];
int dp[maxn];
bool can[maxn];

namespace sub3{
    void prep() {
        const pii nostate = {-1, 0};
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= B; j++) {
                val[i][j] = nostate;
            }
        }
        memset(can, 0, sizeof(can));
        for (int u = 1; u <= n; u++) {
            //init
            for (int i = 0; i <= B; i++) {
                if (val[u][i].fi < 0) {
                    val[u][i] = {0, u};
                    break;
                }
            }
            for (int v : adj[u]) {
                pii cur[B+5];
                for (int i = 0; i <= B; i++) {
                    cur[i] = val[v][i];
                    val[v][i] = nostate;
                }
                int i = 0, j = 0, pos = 0;
                while (pos <= B) {
                    if ((i > B || val[u][i] == nostate) && (j > B || cur[j] == nostate)) break;
                    if (i > B || val[u][i] == nostate) {
                        if (can[cur[j].se]) {
                            ++j;
                            continue;
                        }
                        val[v][pos++] = cur[j];
                        can[cur[j].se] = 1;
                        ++j;
                        continue;
                    }
                    if (j > B || cur[j] == nostate) {
                        if (can[val[u][i].se]) {
                            ++i;
                            continue;
                        }
                        val[v][pos++] = make_pair(val[u][i].fi+1, val[u][i].se);
                        can[val[u][i].se] = 1;
                        ++i;
                        continue;
                    }
                    pii temp = val[u][i];
                    ++temp.fi;
                    if (can[temp.se]) {
                        ++i;
                        continue;
                    }
                    if (can[cur[j].se]) {
                        ++j;
                        continue;
                    }
                    if (temp > cur[j]) {
                        val[v][pos] = temp;
                        can[temp.se] = 1;
                        ++i;
                    }
                    else {
                        val[v][pos] = cur[j];
                        can[cur[j].se] = 1;
                        ++j;
                    }
                    ++pos;
                }
                //reset
                for (int i = 0; i <= B; i++) {
                    if (val[v][i] == nostate) break;
                    can[val[v][i].se] = 0;
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            can[i] = 1;
        }
//        for (int i = 1; i <= n; i++) {
//            cout << "node " << i << ": ";
//            for (int j = 0; j <= min(5, B); j++) {
//                cout << "(" << val[i][j].fi << ", " << val[i][j].se << ") ";
//            }
//            cout << "\n";
//        }
    }
    void solve1(int s, vector<int> &nodes) {
        memset(dp, -1, sizeof(dp));
        dp[s] = 0;
        for (int u : nodes){
            can[u] = 0;
        }
        for (int u = s; u > 1; u--) {
            if (dp[u] == -1) continue;
            for (int v : revadj[u]) {
                maximize(dp[v], dp[u]+1);
            }
        }
        int res = -1;
        for (int i = s; i; i--) {
            if (can[i]) maximize(res, dp[i]);
        }
        cout << res << "\n";
        for (int u : nodes) {
            can[u] = 1;
        }
    }

    void solve2(int s, vector<int> &nodes) {
        for (int u : nodes){
            can[u] = 0;
        }
        int j = 0;
        while (!can[val[s][j].se]) {
            ++j;
        }
        cout << val[s][j].fi << "\n";
        for (int u : nodes) {
            can[u] = 1;
        }
    }

    void solve() {
        //prep val DAG -> case <= B
        prep();
        while (q--) {
            int start, sz;
            cin >> start >> sz;
            vector<int> nodes;
            for (int i = 1; i <= sz; i++) {
                int u;
                cin >> u;
                nodes.pb(u);
            }
            if (sz >= B)
                solve1(start, nodes);
            else
                solve2(start, nodes);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        revadj[v].pb(u);
    }
    return sub3::solve(), 0;
}
/*
5 6 1
2 5
1 3
1 5
2 4
3 5
2 3
5 3 2 3 5

5 6 1
1 3
3 4
3 5
4 5
2 5
2 4
5 5 1 2 3 4 5

5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5

12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8
*/

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