oj.uz

Submission #59446

# Submission time Handle Problem Language Result Execution time Memory
59446 2018-07-22T05:28:17 Z tmwilliamlin168 Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 1321 ms 35708 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5, bs=30;
int n, m, q, dp2[mxN], c[mxN];
vector<int> adj[mxN];
vector<pii> dp1[mxN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool a[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	while(m--) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[v].push_back(u);
	}
	for(int i=0; i<n; ++i) {
		pq.push({0, i});
		for(int v : adj[i]) {
			for(pii p : dp1[v]) {
				pq.push({p.fi+1, p.se});
				if(pq.size()>bs)
					pq.pop();
			}
		}
		while(!pq.empty()) {
			dp1[i].push_back(pq.top());
			pq.pop();
		}
	}
	while(q--) {
		int t, y, ans=-1;
		cin >> t >> y, --t;
		for(int i=0; i<y; ++i) {
			cin >> c[i], --c[i];
			a[c[i]]=1;
		}
		if(y>bs) {
			memset(dp2, -1, 4*(t+1));
			for(int i=0; i<=t; ++i) {
				dp2[i]=a[i]?-n:0;
				for(int v : adj[i])
					dp2[i]=max(dp2[v]+1, dp2[i]);
			}
			ans=max(dp2[t], ans);
		} else {
			for(int i=dp1[t].size()-1; i>=0; --i) {
				if(a[dp1[t][i].se])
					continue;
				ans=dp1[t][i].fi;
				break;
			}
		}
		for(int i=0; i<y; ++i)
			a[c[i]]=0;
		cout << ans << "\n";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Correct 12 ms 5408 KB Output is correct
6 Correct 11 ms 5408 KB Output is correct
7 Correct 11 ms 5536 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 10 ms 5612 KB Output is correct
11 Correct 12 ms 5612 KB Output is correct
12 Correct 10 ms 5616 KB Output is correct
13 Correct 10 ms 5616 KB Output is correct
14 Correct 10 ms 5616 KB Output is correct
15 Correct 9 ms 5616 KB Output is correct
16 Correct 9 ms 5616 KB Output is correct
17 Correct 10 ms 5616 KB Output is correct
18 Correct 9 ms 5616 KB Output is correct
19 Correct 10 ms 5616 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Correct 12 ms 5408 KB Output is correct
6 Correct 11 ms 5408 KB Output is correct
7 Correct 11 ms 5536 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 10 ms 5612 KB Output is correct
11 Correct 12 ms 5612 KB Output is correct
12 Correct 10 ms 5616 KB Output is correct
13 Correct 10 ms 5616 KB Output is correct
14 Correct 10 ms 5616 KB Output is correct
15 Correct 9 ms 5616 KB Output is correct
16 Correct 9 ms 5616 KB Output is correct
17 Correct 10 ms 5616 KB Output is correct
18 Correct 9 ms 5616 KB Output is correct
19 Correct 10 ms 5616 KB Output is correct
20 Correct 271 ms 6608 KB Output is correct
21 Correct 266 ms 6608 KB Output is correct
22 Correct 275 ms 6660 KB Output is correct
23 Correct 276 ms 6716 KB Output is correct
24 Correct 502 ms 30512 KB Output is correct
25 Correct 505 ms 30512 KB Output is correct
26 Correct 459 ms 30512 KB Output is correct
27 Correct 478 ms 35628 KB Output is correct
28 Correct 513 ms 35700 KB Output is correct
29 Correct 462 ms 35708 KB Output is correct
30 Correct 434 ms 35708 KB Output is correct
31 Correct 454 ms 35708 KB Output is correct
32 Correct 427 ms 35708 KB Output is correct
33 Correct 368 ms 35708 KB Output is correct
34 Correct 429 ms 35708 KB Output is correct
35 Correct 385 ms 35708 KB Output is correct
36 Correct 401 ms 35708 KB Output is correct
37 Correct 470 ms 35708 KB Output is correct
38 Correct 425 ms 35708 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Correct 12 ms 5408 KB Output is correct
6 Correct 11 ms 5408 KB Output is correct
7 Correct 11 ms 5536 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 10 ms 5612 KB Output is correct
11 Correct 12 ms 5612 KB Output is correct
12 Correct 10 ms 5616 KB Output is correct
13 Correct 10 ms 5616 KB Output is correct
14 Correct 10 ms 5616 KB Output is correct
15 Correct 9 ms 5616 KB Output is correct
16 Correct 9 ms 5616 KB Output is correct
17 Correct 10 ms 5616 KB Output is correct
18 Correct 9 ms 5616 KB Output is correct
19 Correct 10 ms 5616 KB Output is correct
20 Correct 271 ms 6608 KB Output is correct
21 Correct 266 ms 6608 KB Output is correct
22 Correct 275 ms 6660 KB Output is correct
23 Correct 276 ms 6716 KB Output is correct
24 Correct 502 ms 30512 KB Output is correct
25 Correct 505 ms 30512 KB Output is correct
26 Correct 459 ms 30512 KB Output is correct
27 Correct 478 ms 35628 KB Output is correct
28 Correct 513 ms 35700 KB Output is correct
29 Correct 462 ms 35708 KB Output is correct
30 Correct 434 ms 35708 KB Output is correct
31 Correct 454 ms 35708 KB Output is correct
32 Correct 427 ms 35708 KB Output is correct
33 Correct 368 ms 35708 KB Output is correct
34 Correct 429 ms 35708 KB Output is correct
35 Correct 385 ms 35708 KB Output is correct
36 Correct 401 ms 35708 KB Output is correct
37 Correct 470 ms 35708 KB Output is correct
38 Correct 425 ms 35708 KB Output is correct
39 Correct 611 ms 35708 KB Output is correct
40 Correct 560 ms 35708 KB Output is correct
41 Correct 1321 ms 35708 KB Output is correct
42 Correct 805 ms 35708 KB Output is correct
43 Correct 548 ms 35708 KB Output is correct
44 Incorrect 310 ms 35708 KB Output isn't correct
45 Halted 0 ms 0 KB -