oj.uz

Submission #1030162

# Submission time Handle Problem Language Result Execution time Memory
1030162 2024-07-21T22:03:17 Z SamuellH12 Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 1268 ms 387704 KB 
#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ALL(x) x.begin(), x.end()
#define endl "\n"
#define vi vector<int>
#define pii pair<int,int>
const int MAXN = 1e5 + 5;
const int SQRT = 200;
using namespace std;
 
int block[MAXN], dp[MAXN], tempo;
vi trafo[MAXN], order;
vector<pii> best[MAXN];

void get_order(int n){
	queue<int> fila;
 
	for(int i=1; i<=n; i++)	
		if(dp[i] == 0)
			fila.emplace(i);
 
	while(!fila.empty())
	{
		auto u = fila.front(); fila.pop();
		order.emplace_back(u);
 
		for(auto v : trafo[u])
			if(--dp[v] == 0)
				fila.emplace(v);
	}
 
	reverse(ALL(order));
}
 
void precalc(){
	for(auto u : order)
	{
        best[u].emplace_back(0, u);
		for(auto v : trafo[u])
		{
			// best[u].emplace_back(-1, v);
 
			for(auto [x, w] : best[v])
				if(best[u].back() != pii(x-1, w))
					best[u].emplace_back(x-1, w);	
 
			if(best[u].size() > 2*SQRT)
			{
				sort(ALL(best[u]));
				best[u].resize(SQRT);
			}
		}
 
		sort(ALL(best[u]));
		if(best[u].size() > SQRT) best[u].resize(SQRT);
	}
}
 
int solve(int w){
	for(auto u : order)
	{
		dp[u] = (block[u] == tempo ? -1 : 0);
 
		for(auto v : trafo[u])
			if(~dp[v]) 
				dp[u] = max(dp[u], dp[v]+1);
 
		if(u == w) return dp[u];
	}
	
	assert(false);
	return dp[w];
}
 
int main(){
	optimize;
	int n, m, q;
	cin >> n >> m >> q;
	
	for(int i=0, u, v; i<m; i++)
	{
		cin >> u >> v;
		trafo[v].emplace_back(u);
		dp[u]++;
	}
 
	get_order(n);
	precalc();
 
	int t, y;
	while(q--)
	{
		tempo++;
		cin >> t >> y;
 
		for(int i=0, x; i<y; i++)
			cin >> x, block[x] = tempo;
 
		int ans = -100;
 
		for(auto [x, w] : best[t]) 
			if(block[w] != tempo)
			{
				ans = -x;
				break;
			}
 
		if(ans == -100) ans = solve(t);
		
		cout << ans << endl;
	}
 
	return 0;	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 5156 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 8 ms 6492 KB Output is correct
6 Correct 7 ms 6236 KB Output is correct
7 Correct 10 ms 6484 KB Output is correct
8 Correct 19 ms 8844 KB Output is correct
9 Correct 13 ms 8796 KB Output is correct
10 Correct 13 ms 8820 KB Output is correct
11 Correct 13 ms 8336 KB Output is correct
12 Correct 8 ms 7004 KB Output is correct
13 Correct 12 ms 8524 KB Output is correct
14 Correct 10 ms 7004 KB Output is correct
15 Correct 7 ms 6236 KB Output is correct
16 Correct 10 ms 7004 KB Output is correct
17 Correct 11 ms 7512 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 11 ms 7516 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 5156 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 8 ms 6492 KB Output is correct
6 Correct 7 ms 6236 KB Output is correct
7 Correct 10 ms 6484 KB Output is correct
8 Correct 19 ms 8844 KB Output is correct
9 Correct 13 ms 8796 KB Output is correct
10 Correct 13 ms 8820 KB Output is correct
11 Correct 13 ms 8336 KB Output is correct
12 Correct 8 ms 7004 KB Output is correct
13 Correct 12 ms 8524 KB Output is correct
14 Correct 10 ms 7004 KB Output is correct
15 Correct 7 ms 6236 KB Output is correct
16 Correct 10 ms 7004 KB Output is correct
17 Correct 11 ms 7512 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 11 ms 7516 KB Output is correct
20 Correct 543 ms 11856 KB Output is correct
21 Correct 650 ms 12532 KB Output is correct
22 Correct 577 ms 12088 KB Output is correct
23 Correct 662 ms 12052 KB Output is correct
24 Correct 838 ms 239552 KB Output is correct
25 Correct 997 ms 259252 KB Output is correct
26 Correct 920 ms 249656 KB Output is correct
27 Correct 807 ms 379848 KB Output is correct
28 Correct 745 ms 379892 KB Output is correct
29 Correct 710 ms 379596 KB Output is correct
30 Correct 843 ms 381252 KB Output is correct
31 Correct 983 ms 387704 KB Output is correct
32 Correct 795 ms 381396 KB Output is correct
33 Correct 767 ms 223876 KB Output is correct
34 Correct 802 ms 196300 KB Output is correct
35 Correct 745 ms 221900 KB Output is correct
36 Correct 909 ms 308176 KB Output is correct
37 Correct 933 ms 296148 KB Output is correct
38 Correct 948 ms 308192 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 5156 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 8 ms 6492 KB Output is correct
6 Correct 7 ms 6236 KB Output is correct
7 Correct 10 ms 6484 KB Output is correct
8 Correct 19 ms 8844 KB Output is correct
9 Correct 13 ms 8796 KB Output is correct
10 Correct 13 ms 8820 KB Output is correct
11 Correct 13 ms 8336 KB Output is correct
12 Correct 8 ms 7004 KB Output is correct
13 Correct 12 ms 8524 KB Output is correct
14 Correct 10 ms 7004 KB Output is correct
15 Correct 7 ms 6236 KB Output is correct
16 Correct 10 ms 7004 KB Output is correct
17 Correct 11 ms 7512 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 11 ms 7516 KB Output is correct
20 Correct 543 ms 11856 KB Output is correct
21 Correct 650 ms 12532 KB Output is correct
22 Correct 577 ms 12088 KB Output is correct
23 Correct 662 ms 12052 KB Output is correct
24 Correct 838 ms 239552 KB Output is correct
25 Correct 997 ms 259252 KB Output is correct
26 Correct 920 ms 249656 KB Output is correct
27 Correct 807 ms 379848 KB Output is correct
28 Correct 745 ms 379892 KB Output is correct
29 Correct 710 ms 379596 KB Output is correct
30 Correct 843 ms 381252 KB Output is correct
31 Correct 983 ms 387704 KB Output is correct
32 Correct 795 ms 381396 KB Output is correct
33 Correct 767 ms 223876 KB Output is correct
34 Correct 802 ms 196300 KB Output is correct
35 Correct 745 ms 221900 KB Output is correct
36 Correct 909 ms 308176 KB Output is correct
37 Correct 933 ms 296148 KB Output is correct
38 Correct 948 ms 308192 KB Output is correct
39 Correct 828 ms 246992 KB Output is correct
40 Correct 854 ms 257184 KB Output is correct
41 Correct 881 ms 260812 KB Output is correct
42 Correct 834 ms 247248 KB Output is correct
43 Correct 862 ms 247712 KB Output is correct
44 Correct 494 ms 13208 KB Output is correct
45 Correct 524 ms 12372 KB Output is correct
46 Correct 471 ms 12140 KB Output is correct
47 Correct 537 ms 11860 KB Output is correct
48 Correct 468 ms 11788 KB Output is correct
49 Correct 833 ms 381060 KB Output is correct
50 Correct 1219 ms 379200 KB Output is correct
51 Correct 567 ms 13572 KB Output is correct
52 Correct 793 ms 12804 KB Output is correct
53 Correct 956 ms 308080 KB Output is correct
54 Correct 971 ms 296428 KB Output is correct
55 Incorrect 1268 ms 306896 KB Output isn't correct
56 Halted 0 ms 0 KB -