oj.uz

답안 #954965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954965 2024-03-29T02:10:28 Z ByeWorld Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 430484 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 = 3e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int SQRT = 150;
const int MOD = 998244353;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21592 KB Output is correct
2 Correct 5 ms 21596 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 5 ms 21596 KB Output is correct
5 Correct 9 ms 22444 KB Output is correct
6 Correct 9 ms 22660 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 19 ms 25436 KB Output is correct
9 Correct 20 ms 25180 KB Output is correct
10 Correct 19 ms 25416 KB Output is correct
11 Correct 21 ms 25180 KB Output is correct
12 Correct 14 ms 23900 KB Output is correct
13 Correct 23 ms 25180 KB Output is correct
14 Correct 16 ms 23900 KB Output is correct
15 Correct 12 ms 23180 KB Output is correct
16 Correct 16 ms 23640 KB Output is correct
17 Correct 17 ms 24104 KB Output is correct
18 Correct 13 ms 23644 KB Output is correct
19 Correct 18 ms 24412 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21592 KB Output is correct
2 Correct 5 ms 21596 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 5 ms 21596 KB Output is correct
5 Correct 9 ms 22444 KB Output is correct
6 Correct 9 ms 22660 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 19 ms 25436 KB Output is correct
9 Correct 20 ms 25180 KB Output is correct
10 Correct 19 ms 25416 KB Output is correct
11 Correct 21 ms 25180 KB Output is correct
12 Correct 14 ms 23900 KB Output is correct
13 Correct 23 ms 25180 KB Output is correct
14 Correct 16 ms 23900 KB Output is correct
15 Correct 12 ms 23180 KB Output is correct
16 Correct 16 ms 23640 KB Output is correct
17 Correct 17 ms 24104 KB Output is correct
18 Correct 13 ms 23644 KB Output is correct
19 Correct 18 ms 24412 KB Output is correct
20 Correct 1981 ms 28272 KB Output is correct
21 Correct 1960 ms 29680 KB Output is correct
22 Correct 1986 ms 29792 KB Output is correct
23 Correct 1995 ms 31840 KB Output is correct
24 Correct 1432 ms 312172 KB Output is correct
25 Correct 1432 ms 320744 KB Output is correct
26 Correct 1445 ms 320772 KB Output is correct
27 Correct 1499 ms 430172 KB Output is correct
28 Correct 1522 ms 430484 KB Output is correct
29 Correct 1488 ms 430480 KB Output is correct
30 Correct 1633 ms 430252 KB Output is correct
31 Correct 1884 ms 419860 KB Output is correct
32 Correct 1630 ms 429644 KB Output is correct
33 Correct 1210 ms 274248 KB Output is correct
34 Correct 1130 ms 238780 KB Output is correct
35 Correct 1215 ms 272488 KB Output is correct
36 Correct 1499 ms 352656 KB Output is correct
37 Correct 1525 ms 328992 KB Output is correct
38 Correct 1513 ms 353560 KB Output is correct

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21592 KB Output is correct
2 Correct 5 ms 21596 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 5 ms 21596 KB Output is correct
5 Correct 9 ms 22444 KB Output is correct
6 Correct 9 ms 22660 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 19 ms 25436 KB Output is correct
9 Correct 20 ms 25180 KB Output is correct
10 Correct 19 ms 25416 KB Output is correct
11 Correct 21 ms 25180 KB Output is correct
12 Correct 14 ms 23900 KB Output is correct
13 Correct 23 ms 25180 KB Output is correct
14 Correct 16 ms 23900 KB Output is correct
15 Correct 12 ms 23180 KB Output is correct
16 Correct 16 ms 23640 KB Output is correct
17 Correct 17 ms 24104 KB Output is correct
18 Correct 13 ms 23644 KB Output is correct
19 Correct 18 ms 24412 KB Output is correct
20 Correct 1981 ms 28272 KB Output is correct
21 Correct 1960 ms 29680 KB Output is correct
22 Correct 1986 ms 29792 KB Output is correct
23 Correct 1995 ms 31840 KB Output is correct
24 Correct 1432 ms 312172 KB Output is correct
25 Correct 1432 ms 320744 KB Output is correct
26 Correct 1445 ms 320772 KB Output is correct
27 Correct 1499 ms 430172 KB Output is correct
28 Correct 1522 ms 430484 KB Output is correct
29 Correct 1488 ms 430480 KB Output is correct
30 Correct 1633 ms 430252 KB Output is correct
31 Correct 1884 ms 419860 KB Output is correct
32 Correct 1630 ms 429644 KB Output is correct
33 Correct 1210 ms 274248 KB Output is correct
34 Correct 1130 ms 238780 KB Output is correct
35 Correct 1215 ms 272488 KB Output is correct
36 Correct 1499 ms 352656 KB Output is correct
37 Correct 1525 ms 328992 KB Output is correct
38 Correct 1513 ms 353560 KB Output is correct
39 Correct 1549 ms 316012 KB Output is correct
40 Correct 1430 ms 317236 KB Output is correct
41 Correct 1416 ms 317764 KB Output is correct
42 Correct 1447 ms 318720 KB Output is correct
43 Correct 1384 ms 316084 KB Output is correct
44 Execution timed out 2041 ms 30108 KB Time limit exceeded
45 Halted 0 ms 0 KB -