oj.uz

Submission #670202

# Submission time Handle Problem Language Result Execution time Memory
670202 2022-12-08T09:37:37 Z hafo Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 352 ms 25044 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e15 + 69;
const int sz = 320;

int n, m, q, u, v, t, y, c, id[maxn], d[maxn];
bool vis[maxn];
pa f[sz][maxn], check[sz];
vector<int> g[maxn], topo, arc[maxn];

void dfs(int u) {
    vis[u] = 1;
    for(auto v:g[u])
        if(!vis[v]) dfs(v);
    topo.pb(u);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m>>q;
    while(m--) {
        cin>>u>>v;
        g[u].pb(v);
        arc[v].pb(u);
    }

    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i);
    reverse(all(topo));

    for(int i = 1; i <= n; i++)
    for(int j = 0; j < sz; j++) f[j][i] = {0, (j == 0 ? i:-1)};
    for(auto u:topo) {
        for(auto v:g[u]) {
            int j = 0;
            fill_n(check, sz, make_pair(-1, -1));
            for(int i = 0; i < sz; i++) {
                if(i && check[i - 1].fi != -1) {
                    check[i] = f[i][v];
                    f[i][v] = check[i - 1];
                }
                while(j < sz - 1 && f[j][u].se != -1 && f[j][u].fi + 1 <= f[i][v].fi) j++;
                if(f[j][u].se != -1 && f[j][u].fi + 1 > f[i][v].fi) {
                    check[i] = f[i][v];
                    f[i][v] = {f[j][u].fi + 1, f[j][u].se};
                    j++;
                }
            }
        }
    }

    for(int k = 1; k <= q; k++) {
        cin>>t>>y;
        for(int i = 0; i < y; i++) {
            cin>>c;
            id[c] = k;
        }

        if(y >= sz) {
            fill_n(d, n + 1, -1);
            d[t] = 0;
            int ans = -1;
            if(id[t] != k) ans = 0;
            bool ok = 0;

            for(int i = topo.size() - 1; i >= 0; i--) {
                int u = topo[i];
                if(d[u] == -1 || (u != t && !ok)) continue;
                if(u > t) continue;
                if(u == t) ok = 1;
                for(auto v:arc[u]) {
                    maxi(d[v], d[u] + 1);
                    if(v <= t && id[v] != k) maxi(ans, d[v]);
                }
            }
            cout<<ans<<"\n";
        } else {
            int ans = -1;
            for(int i = 0; i < sz; i++) {
                int u = f[i][t].se;
                if(u == -1 || id[u] == k || u > t) continue;
                maxi(ans, f[i][t].fi);
            }
            cout<<ans<<"\n";
        }
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6692 KB Output is correct
2 Correct 4 ms 6740 KB Output is correct
3 Correct 3 ms 6696 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 8 ms 9364 KB Output is correct
6 Correct 8 ms 9264 KB Output is correct
7 Correct 7 ms 9300 KB Output is correct
8 Correct 8 ms 9436 KB Output is correct
9 Correct 7 ms 9428 KB Output is correct
10 Correct 7 ms 9428 KB Output is correct
11 Correct 7 ms 9300 KB Output is correct
12 Correct 10 ms 9396 KB Output is correct
13 Correct 9 ms 9260 KB Output is correct
14 Correct 7 ms 9300 KB Output is correct
15 Correct 7 ms 9300 KB Output is correct
16 Correct 7 ms 9320 KB Output is correct
17 Correct 8 ms 9392 KB Output is correct
18 Correct 8 ms 9300 KB Output is correct
19 Correct 7 ms 9300 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6692 KB Output is correct
2 Correct 4 ms 6740 KB Output is correct
3 Correct 3 ms 6696 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 8 ms 9364 KB Output is correct
6 Correct 8 ms 9264 KB Output is correct
7 Correct 7 ms 9300 KB Output is correct
8 Correct 8 ms 9436 KB Output is correct
9 Correct 7 ms 9428 KB Output is correct
10 Correct 7 ms 9428 KB Output is correct
11 Correct 7 ms 9300 KB Output is correct
12 Correct 10 ms 9396 KB Output is correct
13 Correct 9 ms 9260 KB Output is correct
14 Correct 7 ms 9300 KB Output is correct
15 Correct 7 ms 9300 KB Output is correct
16 Correct 7 ms 9320 KB Output is correct
17 Correct 8 ms 9392 KB Output is correct
18 Correct 8 ms 9300 KB Output is correct
19 Correct 7 ms 9300 KB Output is correct
20 Correct 286 ms 13384 KB Output is correct
21 Correct 352 ms 13376 KB Output is correct
22 Correct 340 ms 13340 KB Output is correct
23 Runtime error 243 ms 25044 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6692 KB Output is correct
2 Correct 4 ms 6740 KB Output is correct
3 Correct 3 ms 6696 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 8 ms 9364 KB Output is correct
6 Correct 8 ms 9264 KB Output is correct
7 Correct 7 ms 9300 KB Output is correct
8 Correct 8 ms 9436 KB Output is correct
9 Correct 7 ms 9428 KB Output is correct
10 Correct 7 ms 9428 KB Output is correct
11 Correct 7 ms 9300 KB Output is correct
12 Correct 10 ms 9396 KB Output is correct
13 Correct 9 ms 9260 KB Output is correct
14 Correct 7 ms 9300 KB Output is correct
15 Correct 7 ms 9300 KB Output is correct
16 Correct 7 ms 9320 KB Output is correct
17 Correct 8 ms 9392 KB Output is correct
18 Correct 8 ms 9300 KB Output is correct
19 Correct 7 ms 9300 KB Output is correct
20 Correct 286 ms 13384 KB Output is correct
21 Correct 352 ms 13376 KB Output is correct
22 Correct 340 ms 13340 KB Output is correct
23 Runtime error 243 ms 25044 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -