oj.uz

Submission #967472

# Submission time Handle Problem Language Result Execution time Memory
967472 2024-04-22T07:21:20 Z Tuanlinh123 Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 252340 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=300;
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();
        if (sz(At[u]))
        {
            vector <pll> val; 
            best[u]=best[At[u][0]];
            for (ll i=1; i<sz(At[u]); i++)
            {
                ll v=At[u][i];
                for (ll p1=0, p2=0; p1<sz(best[u]) || p2<sz(best[v]);)
                {
                    if (p1==sz(best[u]) || (p2<sz(best[v]) && best[u][p1]<best[v][p2]))
                        val.pb(best[v][p2]), p2++;
                    else val.pb(best[u][p1]), p1++;
                }
                best[u].clear();
                for (auto [x, v]:val)
                    if (!seen[v])
                    {
                        seen[v]=1, best[u].pb({x, v});
                        if (sz(best[u])==s) break;
                    }
                for (auto [x, v]:best[u]) seen[v]=0;
                val.clear();
            }
        }
        for (auto &[x, v]:best[u]) x++;
        if (sz(best[u])<s) best[u].pb({0, u});
        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 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 4 ms 8068 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 8 ms 10076 KB Output is correct
9 Correct 9 ms 10076 KB Output is correct
10 Correct 10 ms 10076 KB Output is correct
11 Correct 9 ms 9676 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct
14 Correct 7 ms 9048 KB Output is correct
15 Correct 6 ms 8284 KB Output is correct
16 Correct 7 ms 9048 KB Output is correct
17 Correct 7 ms 9308 KB Output is correct
18 Correct 5 ms 8796 KB Output is correct
19 Correct 7 ms 9308 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 4 ms 8068 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 8 ms 10076 KB Output is correct
9 Correct 9 ms 10076 KB Output is correct
10 Correct 10 ms 10076 KB Output is correct
11 Correct 9 ms 9676 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct
14 Correct 7 ms 9048 KB Output is correct
15 Correct 6 ms 8284 KB Output is correct
16 Correct 7 ms 9048 KB Output is correct
17 Correct 7 ms 9308 KB Output is correct
18 Correct 5 ms 8796 KB Output is correct
19 Correct 7 ms 9308 KB Output is correct
20 Correct 676 ms 12912 KB Output is correct
21 Correct 628 ms 12408 KB Output is correct
22 Correct 655 ms 12884 KB Output is correct
23 Correct 744 ms 12688 KB Output is correct
24 Correct 675 ms 234108 KB Output is correct
25 Correct 725 ms 241988 KB Output is correct
26 Correct 704 ms 241648 KB Output is correct
27 Correct 629 ms 251884 KB Output is correct
28 Correct 630 ms 251984 KB Output is correct
29 Correct 642 ms 252008 KB Output is correct
30 Correct 641 ms 251276 KB Output is correct
31 Correct 644 ms 246856 KB Output is correct
32 Correct 620 ms 251172 KB Output is correct
33 Correct 581 ms 190964 KB Output is correct
34 Correct 571 ms 165452 KB Output is correct
35 Correct 572 ms 190028 KB Output is correct
36 Correct 640 ms 236932 KB Output is correct
37 Correct 627 ms 227844 KB Output is correct
38 Correct 683 ms 238564 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 4 ms 8068 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 8 ms 10076 KB Output is correct
9 Correct 9 ms 10076 KB Output is correct
10 Correct 10 ms 10076 KB Output is correct
11 Correct 9 ms 9676 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct
14 Correct 7 ms 9048 KB Output is correct
15 Correct 6 ms 8284 KB Output is correct
16 Correct 7 ms 9048 KB Output is correct
17 Correct 7 ms 9308 KB Output is correct
18 Correct 5 ms 8796 KB Output is correct
19 Correct 7 ms 9308 KB Output is correct
20 Correct 676 ms 12912 KB Output is correct
21 Correct 628 ms 12408 KB Output is correct
22 Correct 655 ms 12884 KB Output is correct
23 Correct 744 ms 12688 KB Output is correct
24 Correct 675 ms 234108 KB Output is correct
25 Correct 725 ms 241988 KB Output is correct
26 Correct 704 ms 241648 KB Output is correct
27 Correct 629 ms 251884 KB Output is correct
28 Correct 630 ms 251984 KB Output is correct
29 Correct 642 ms 252008 KB Output is correct
30 Correct 641 ms 251276 KB Output is correct
31 Correct 644 ms 246856 KB Output is correct
32 Correct 620 ms 251172 KB Output is correct
33 Correct 581 ms 190964 KB Output is correct
34 Correct 571 ms 165452 KB Output is correct
35 Correct 572 ms 190028 KB Output is correct
36 Correct 640 ms 236932 KB Output is correct
37 Correct 627 ms 227844 KB Output is correct
38 Correct 683 ms 238564 KB Output is correct
39 Correct 707 ms 235660 KB Output is correct
40 Correct 714 ms 237632 KB Output is correct
41 Correct 672 ms 239244 KB Output is correct
42 Correct 1316 ms 239836 KB Output is correct
43 Correct 773 ms 238416 KB Output is correct
44 Correct 712 ms 13196 KB Output is correct
45 Correct 681 ms 13016 KB Output is correct
46 Correct 667 ms 13272 KB Output is correct
47 Correct 712 ms 12616 KB Output is correct
48 Correct 666 ms 12880 KB Output is correct
49 Correct 869 ms 251780 KB Output is correct
50 Correct 826 ms 250936 KB Output is correct
51 Correct 640 ms 12788 KB Output is correct
52 Correct 643 ms 12528 KB Output is correct
53 Correct 741 ms 237244 KB Output is correct
54 Correct 695 ms 227660 KB Output is correct
55 Correct 688 ms 236780 KB Output is correct
56 Correct 665 ms 227392 KB Output is correct
57 Correct 688 ms 12876 KB Output is correct
58 Correct 695 ms 13068 KB Output is correct
59 Correct 647 ms 12896 KB Output is correct
60 Correct 682 ms 12708 KB Output is correct
61 Correct 1014 ms 252104 KB Output is correct
62 Correct 1223 ms 237820 KB Output is correct
63 Correct 1279 ms 227356 KB Output is correct
64 Correct 1755 ms 252340 KB Output is correct
65 Execution timed out 2072 ms 237024 KB Time limit exceeded
66 Halted 0 ms 0 KB -