oj.uz

Submission #967450

# Submission time Handle Problem Language Result Execution time Memory
967450 2024-04-22T06:37:27 Z Tuanlinh123 Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 119940 KB 
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=100005, s=100;
ll deg[maxn], seen[maxn];
vector <pll> best[maxn];
vector <ll> A[maxn], At[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, q; cin >> n >> m >> q;
    for (ll i=1; i<=m; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v), At[v].pb(u), deg[v]++;
    }
    queue <ll> Q;
    for (ll i=1; i<=n; i++)
        if (!deg[i]) Q.push(i);
    while (sz(Q))
    {
        ll u=Q.front(); Q.pop();
        vector <pll> val={{-1, u}};
        for (ll v:At[u]) 
            for (pll b:best[v])
                val.pb(b);
        sort(val.begin(), val.end(), greater<pll>());
        for (auto [x, v]:val)
            if (!seen[v] && sz(best[u])<s) 
                seen[v]=1, best[u].pb({x+1, v});
        for (auto [x, v]:best[u]) seen[v]=0;
        for (ll v:A[u])
        {
            deg[v]--;
            if (!deg[v]) Q.push(v);
        }
    }
    for (ll i=1; i<=q; i++)
    {
        ll X, x, ans=-1; cin >> X >> x;
        vector <ll> a(x);
        for (ll &i:a) cin >> i;
        if (x>=s)
        {
            queue <ll> q;
            vector <ll> dp(n+5, 0), deg(n+5, 0);
            for (ll i=1; i<=n; i++) deg[i]=sz(At[i]), !deg[i]?q.push(i),0:0;
            for (ll i:a) dp[i]=-1e9;
            while (sz(q))
            {
                ll u=q.front(); q.pop();
                for (ll v:At[u]) 
                    dp[u]=max(dp[u], dp[v]+1);
                for (ll v:A[u])
                {
                    deg[v]--;
                    if (!deg[v]) q.push(v);
                }
            }
            if (dp[X]>=0) ans=dp[X];
        }
        else
        {
            for (ll j:a) seen[j]=1;
            for (auto [x, v]:best[X])
                if (!seen[v]) {ans=x; break;}
            for (ll j:a) seen[j]=0;
        } 
        cout << ans << "\n";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7348 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 5 ms 7952 KB Output is correct
6 Correct 5 ms 7772 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 6 ms 8572 KB Output is correct
9 Correct 7 ms 8536 KB Output is correct
10 Correct 8 ms 8540 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct
12 Correct 6 ms 8128 KB Output is correct
13 Correct 7 ms 8284 KB Output is correct
14 Correct 7 ms 8296 KB Output is correct
15 Correct 5 ms 8028 KB Output is correct
16 Correct 6 ms 8028 KB Output is correct
17 Correct 8 ms 8284 KB Output is correct
18 Correct 6 ms 8028 KB Output is correct
19 Correct 7 ms 8280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7348 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 5 ms 7952 KB Output is correct
6 Correct 5 ms 7772 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 6 ms 8572 KB Output is correct
9 Correct 7 ms 8536 KB Output is correct
10 Correct 8 ms 8540 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct
12 Correct 6 ms 8128 KB Output is correct
13 Correct 7 ms 8284 KB Output is correct
14 Correct 7 ms 8296 KB Output is correct
15 Correct 5 ms 8028 KB Output is correct
16 Correct 6 ms 8028 KB Output is correct
17 Correct 8 ms 8284 KB Output is correct
18 Correct 6 ms 8028 KB Output is correct
19 Correct 7 ms 8280 KB Output is correct
20 Correct 1152 ms 11340 KB Output is correct
21 Correct 1118 ms 13444 KB Output is correct
22 Correct 1128 ms 12916 KB Output is correct
23 Correct 1063 ms 14020 KB Output is correct
24 Correct 704 ms 94548 KB Output is correct
25 Correct 737 ms 96204 KB Output is correct
26 Correct 755 ms 95836 KB Output is correct
27 Correct 459 ms 119576 KB Output is correct
28 Correct 442 ms 119940 KB Output is correct
29 Correct 436 ms 119572 KB Output is correct
30 Correct 499 ms 118864 KB Output is correct
31 Correct 627 ms 116900 KB Output is correct
32 Correct 546 ms 119024 KB Output is correct
33 Correct 485 ms 82072 KB Output is correct
34 Correct 545 ms 74660 KB Output is correct
35 Correct 477 ms 81476 KB Output is correct
36 Correct 591 ms 100584 KB Output is correct
37 Correct 699 ms 96068 KB Output is correct
38 Correct 582 ms 100744 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7348 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 5 ms 7952 KB Output is correct
6 Correct 5 ms 7772 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 6 ms 8572 KB Output is correct
9 Correct 7 ms 8536 KB Output is correct
10 Correct 8 ms 8540 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct
12 Correct 6 ms 8128 KB Output is correct
13 Correct 7 ms 8284 KB Output is correct
14 Correct 7 ms 8296 KB Output is correct
15 Correct 5 ms 8028 KB Output is correct
16 Correct 6 ms 8028 KB Output is correct
17 Correct 8 ms 8284 KB Output is correct
18 Correct 6 ms 8028 KB Output is correct
19 Correct 7 ms 8280 KB Output is correct
20 Correct 1152 ms 11340 KB Output is correct
21 Correct 1118 ms 13444 KB Output is correct
22 Correct 1128 ms 12916 KB Output is correct
23 Correct 1063 ms 14020 KB Output is correct
24 Correct 704 ms 94548 KB Output is correct
25 Correct 737 ms 96204 KB Output is correct
26 Correct 755 ms 95836 KB Output is correct
27 Correct 459 ms 119576 KB Output is correct
28 Correct 442 ms 119940 KB Output is correct
29 Correct 436 ms 119572 KB Output is correct
30 Correct 499 ms 118864 KB Output is correct
31 Correct 627 ms 116900 KB Output is correct
32 Correct 546 ms 119024 KB Output is correct
33 Correct 485 ms 82072 KB Output is correct
34 Correct 545 ms 74660 KB Output is correct
35 Correct 477 ms 81476 KB Output is correct
36 Correct 591 ms 100584 KB Output is correct
37 Correct 699 ms 96068 KB Output is correct
38 Correct 582 ms 100744 KB Output is correct
39 Correct 732 ms 95152 KB Output is correct
40 Correct 696 ms 94964 KB Output is correct
41 Execution timed out 2072 ms 95496 KB Time limit exceeded
42 Halted 0 ms 0 KB -