oj.uz

Submission #900574

# Submission time Handle Problem Language Result Execution time Memory
900574 2024-01-08T14:52:33 Z falaz Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 243028 KB 
#include <bits/stdc++.h> 
using namespace std;

#define endl '\n'
#define int long long

#define F first 
#define S second

const int N = 1e5 + 3, SQ = 1000;
int n, m, q, dis[N];
vector<int> radj[N];
queue<int> qu;
bool mark[N];
vector<pair<int, int>> vec[N];

void bfs() {
	while(qu.size()) {
		int v = qu.front();
		mark[v] = false;
		qu.pop();
		for (auto u : radj[v]) 
			if (dis[v] + 1 > dis[u]) {
				dis[u] = dis[v] + 1;
				if (!mark[u]) {
					qu.push(u);
					mark[u] = true;
				}
			}
	}
}

signed main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		radj[u].push_back(v);
	}
	set<pair<int, int>> st;
	for (int i = 1; i <= n; i++) { 
		if (radj[i].size() == 0)
			vec[i].push_back({i, 0});
		else {
			for (auto v : radj[i]) {
				for (auto u : vec[v]) {
					if (dis[u.F] == 0) {
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					else if(dis[u.F] < u.S + 1) {
						st.erase({dis[u.F], u.F});
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					if (st.size() > SQ) {
						int f = st.begin()->S;
						dis[f] = 0;
						st.erase(st.begin());
					}
				}
			}
			while (st.size()) {
				int v = st.begin()->second, f = st.begin()->first;
				st.erase(st.begin());
				vec[i].push_back({v, f});
				dis[v] = 0;
			}
			vec[i].push_back({i, 0});
			sort(vec[i].begin(), vec[i].end());
		}
	}
	while (q--) {
		int t, y;
		cin >> t >> y;
		int c[y + 1];
		c[y] = n + 1;
		for (int i = 0; i < y; i++)
			cin >> c[i];
		if (y <= SQ) {
			int p = 0, ans = -1;
			for (int i = 0; i < int32_t(vec[t].size()); i++) {
				while (c[p] < vec[t][i].F)
					p++;
				if (vec[t][i].F != c[p]) 
					ans = max(vec[t][i].S, ans);
			}
			cout << ans << endl;
		}
		else {
			qu.push(t);
			bfs();
			int p = 0, ans = -1;
			for (int i = 1; i <= t; i++) {
				while (c[p] < i)
					p++;
				if (i != c[p]) 
					ans = max(ans, dis[i]);
				dis[i] = 0;
			}
			cout << ans << endl;
		}
	}	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 7 ms 5980 KB Output is correct
8 Correct 71 ms 15188 KB Output is correct
9 Correct 71 ms 15188 KB Output is correct
10 Correct 72 ms 15188 KB Output is correct
11 Correct 50 ms 11620 KB Output is correct
12 Correct 21 ms 7772 KB Output is correct
13 Correct 47 ms 11356 KB Output is correct
14 Correct 54 ms 11092 KB Output is correct
15 Correct 23 ms 7500 KB Output is correct
16 Correct 53 ms 11228 KB Output is correct
17 Correct 49 ms 11000 KB Output is correct
18 Correct 23 ms 7516 KB Output is correct
19 Correct 47 ms 10872 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 7 ms 5980 KB Output is correct
8 Correct 71 ms 15188 KB Output is correct
9 Correct 71 ms 15188 KB Output is correct
10 Correct 72 ms 15188 KB Output is correct
11 Correct 50 ms 11620 KB Output is correct
12 Correct 21 ms 7772 KB Output is correct
13 Correct 47 ms 11356 KB Output is correct
14 Correct 54 ms 11092 KB Output is correct
15 Correct 23 ms 7500 KB Output is correct
16 Correct 53 ms 11228 KB Output is correct
17 Correct 49 ms 11000 KB Output is correct
18 Correct 23 ms 7516 KB Output is correct
19 Correct 47 ms 10872 KB Output is correct
20 Correct 441 ms 19352 KB Output is correct
21 Correct 175 ms 19028 KB Output is correct
22 Correct 438 ms 19028 KB Output is correct
23 Correct 501 ms 19024 KB Output is correct
24 Execution timed out 2067 ms 243028 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Correct 7 ms 5980 KB Output is correct
8 Correct 71 ms 15188 KB Output is correct
9 Correct 71 ms 15188 KB Output is correct
10 Correct 72 ms 15188 KB Output is correct
11 Correct 50 ms 11620 KB Output is correct
12 Correct 21 ms 7772 KB Output is correct
13 Correct 47 ms 11356 KB Output is correct
14 Correct 54 ms 11092 KB Output is correct
15 Correct 23 ms 7500 KB Output is correct
16 Correct 53 ms 11228 KB Output is correct
17 Correct 49 ms 11000 KB Output is correct
18 Correct 23 ms 7516 KB Output is correct
19 Correct 47 ms 10872 KB Output is correct
20 Correct 441 ms 19352 KB Output is correct
21 Correct 175 ms 19028 KB Output is correct
22 Correct 438 ms 19028 KB Output is correct
23 Correct 501 ms 19024 KB Output is correct
24 Execution timed out 2067 ms 243028 KB Time limit exceeded
25 Halted 0 ms 0 KB -