oj.uz

Submission #954966

# Submission time Handle Problem Language Result Execution time Memory
954966 2024-03-29T02:11:46 Z ByeWorld Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 15252 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 1e5+10;
const ll INF = 2e18+10;
const int SQRT = 200;

int n, m, q;
vector <int> adj[MAXN];
vector <pii> best[MAXN], que;
vector <int> vec[MAXN];
int ans;
int busy[MAXN], vis[MAXN];
int day, day2;

void dfs(int nw, int dis){
    if(busy[nw] != day) ans = max(ans, dis);
    vis[nw] = day2;
    for(auto nx : adj[nw]){
        if(vis[nx] != day2) dfs(nx, dis+1);
    }
}
signed main() {
	cin >> n >> m >> q;
	for(int i=1; i<=m; i++){
        int u, v; cin >> u >> v;
        adj[v].pb(u);
    }
    for(int i=1; i<=n; i++){
        vector <pii> coba;
        coba.pb({0, i});
        for(auto nx : adj[i]){
            for(auto in : best[nx]) coba.pb({in.fi+1, in.se});
        }
        sort(coba.rbegin(), coba.rend());
        
        day++;
        for(auto in : coba){
            if(busy[in.se] == day) continue;
            busy[in.se] = day;
            best[i].pb(in);
            if(best[i].size() == SQRT) break;
        }
    }
    // for(int i=1; i<=n; i++){
    //     cout << "\ni" << i << "\n";
    //     for(auto in:best[i]) cout << in.fi << ' ' << in.se << '\n';
    // }
    // exit(0);
    for(int i=1; i<=q; i++){
        int sta, siz; cin >> sta >> siz;
        ans = -1;
        for(int j=0; j<siz; j++){
            int x; cin >> x;
            vec[i].pb(x);
        }
        if(siz >= SQRT){
            day++; day2++;
            vector <int> dp; 
            dp.resize(sta+2, -1); 
            
            dp[sta] = 0;
            for(int nw=sta; nw>=1; nw--){
                if(dp[nw]==-1) continue;
                for(auto nx : adj[nw]) dp[nx] = max(dp[nx], dp[nw]+1);
            }
            for(auto in : vec[i]) busy[in] = day;
            for(int nw=sta; nw>=1; nw--){
                if(busy[nw] == day) continue;
                ans = max(ans, dp[nw]);
            }
        
        } else {
            day++;
            for(auto in : vec[i]) busy[in] = day;
            for(auto in : best[sta]){
                if(busy[in.se] == day) continue;
                ans = in.fi;
                break;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 7864 KB Output is correct
5 Correct 6 ms 8864 KB Output is correct
6 Correct 6 ms 9048 KB Output is correct
7 Correct 6 ms 8792 KB Output is correct
8 Correct 20 ms 11792 KB Output is correct
9 Correct 20 ms 11612 KB Output is correct
10 Correct 20 ms 11680 KB Output is correct
11 Correct 21 ms 11608 KB Output is correct
12 Correct 13 ms 10328 KB Output is correct
13 Correct 23 ms 11356 KB Output is correct
14 Correct 17 ms 10332 KB Output is correct
15 Correct 11 ms 9564 KB Output is correct
16 Correct 16 ms 10264 KB Output is correct
17 Correct 16 ms 10588 KB Output is correct
18 Correct 10 ms 10076 KB Output is correct
19 Correct 17 ms 10844 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 7864 KB Output is correct
5 Correct 6 ms 8864 KB Output is correct
6 Correct 6 ms 9048 KB Output is correct
7 Correct 6 ms 8792 KB Output is correct
8 Correct 20 ms 11792 KB Output is correct
9 Correct 20 ms 11612 KB Output is correct
10 Correct 20 ms 11680 KB Output is correct
11 Correct 21 ms 11608 KB Output is correct
12 Correct 13 ms 10328 KB Output is correct
13 Correct 23 ms 11356 KB Output is correct
14 Correct 17 ms 10332 KB Output is correct
15 Correct 11 ms 9564 KB Output is correct
16 Correct 16 ms 10264 KB Output is correct
17 Correct 16 ms 10588 KB Output is correct
18 Correct 10 ms 10076 KB Output is correct
19 Correct 17 ms 10844 KB Output is correct
20 Execution timed out 2029 ms 15252 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 7864 KB Output is correct
5 Correct 6 ms 8864 KB Output is correct
6 Correct 6 ms 9048 KB Output is correct
7 Correct 6 ms 8792 KB Output is correct
8 Correct 20 ms 11792 KB Output is correct
9 Correct 20 ms 11612 KB Output is correct
10 Correct 20 ms 11680 KB Output is correct
11 Correct 21 ms 11608 KB Output is correct
12 Correct 13 ms 10328 KB Output is correct
13 Correct 23 ms 11356 KB Output is correct
14 Correct 17 ms 10332 KB Output is correct
15 Correct 11 ms 9564 KB Output is correct
16 Correct 16 ms 10264 KB Output is correct
17 Correct 16 ms 10588 KB Output is correct
18 Correct 10 ms 10076 KB Output is correct
19 Correct 17 ms 10844 KB Output is correct
20 Execution timed out 2029 ms 15252 KB Time limit exceeded
21 Halted 0 ms 0 KB -