oj.uz

Submission #533248

# Submission time Handle Problem Language Result Execution time Memory
533248 2022-03-05T07:51:11 Z rk42745417 None (JOI16_ho_t3) C++17
26 / 100
 2500 ms 13832 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
static int LamyIsCute = []() {
	EmiliaMyWife
		return 48763;
}();

const int N = 1e5 + 25, M = 2e5 + 25;
vector<pair<int, int>> edge[N];
int add[M], ans[M], init_dis[N], dis[N];
int n;

void init_bfs() {
	memset(init_dis, 0x3f, sizeof init_dis);
	init_dis[1] = 0;
	queue<int> bfs;
	bfs.push(1);
	while(!bfs.empty()) {
		int u = bfs.front();
		bfs.pop();
		for(const auto &[v, _] : edge[u]) {
			if(init_dis[v] > init_dis[u] + 1) {
				init_dis[v] = init_dis[u] + 1;
				bfs.push(v);
			}
		}
	}
}

int solve(int t) {
	if(~ans[t])
		return ans[t];
	memset(dis, 0x3f, sizeof dis);
	queue<int> bfs;
	dis[1] = 0;
	bfs.push(1);
	while(!bfs.empty()) {
		int u = bfs.front();
		bfs.pop();
		for(const auto &[v, c] : edge[u]) {
			if(add[c] <= t)
				continue;
			if(dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				bfs.push(v);
			}
		}
	}
	ans[t] = 0;
	for(int i = 1; i <= n; i++)
		ans[t] += dis[i] != init_dis[i];
	return ans[t];
}

signed main() {
	int m, q;
	cin >> n >> m >> q;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		edge[u].push_back({v, i});
		edge[v].push_back({u, i});
	}
	for(int i = 1, x; i <= q; i++) {
		cin >> x;
		add[x] = i;
	}
	for(int i = 1; i <= m; i++)
		if(add[i] == 0)
			add[i] = INF;

	init_bfs();

	memset(ans, -1, sizeof ans);
	for(int i = 1; i <= q; i++) {
		if(~ans[i])
			continue;
		solve(i);
		int l = i, r = q + 1;
		while(l < r) {
			int m = l + r >> 1;
			if(solve(m) > ans[i])
				r = m;
			else
				l = m + 1;
		}
		for(int j = i + 1; j < l; j++)
			ans[j] = ans[i];
	}
	for(int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

Compilation message

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |    int m = l + r >> 1;
      |            ~~^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4164 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4208 KB Output is correct
6 Correct 3 ms 4200 KB Output is correct
7 Correct 3 ms 4172 KB Output is correct
8 Correct 3 ms 4172 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4164 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4208 KB Output is correct
6 Correct 3 ms 4200 KB Output is correct
7 Correct 3 ms 4172 KB Output is correct
8 Correct 3 ms 4172 KB Output is correct
9 Correct 326 ms 13776 KB Output is correct
10 Correct 327 ms 13636 KB Output is correct
11 Correct 104 ms 13304 KB Output is correct
12 Correct 223 ms 13480 KB Output is correct
13 Correct 268 ms 13544 KB Output is correct
14 Correct 259 ms 13508 KB Output is correct
15 Correct 45 ms 9844 KB Output is correct
16 Correct 140 ms 8964 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1481 ms 13832 KB Output is correct
2 Correct 1331 ms 13696 KB Output is correct
3 Correct 397 ms 11344 KB Output is correct
4 Correct 712 ms 13424 KB Output is correct
5 Correct 574 ms 13400 KB Output is correct
6 Correct 682 ms 13408 KB Output is correct
7 Correct 245 ms 8976 KB Output is correct
8 Correct 381 ms 8896 KB Output is correct
9 Correct 101 ms 8760 KB Output is correct
10 Correct 118 ms 8792 KB Output is correct
11 Execution timed out 2515 ms 13296 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4164 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4208 KB Output is correct
6 Correct 3 ms 4200 KB Output is correct
7 Correct 3 ms 4172 KB Output is correct
8 Correct 3 ms 4172 KB Output is correct
9 Correct 326 ms 13776 KB Output is correct
10 Correct 327 ms 13636 KB Output is correct
11 Correct 104 ms 13304 KB Output is correct
12 Correct 223 ms 13480 KB Output is correct
13 Correct 268 ms 13544 KB Output is correct
14 Correct 259 ms 13508 KB Output is correct
15 Correct 45 ms 9844 KB Output is correct
16 Correct 140 ms 8964 KB Output is correct
17 Correct 1481 ms 13832 KB Output is correct
18 Correct 1331 ms 13696 KB Output is correct
19 Correct 397 ms 11344 KB Output is correct
20 Correct 712 ms 13424 KB Output is correct
21 Correct 574 ms 13400 KB Output is correct
22 Correct 682 ms 13408 KB Output is correct
23 Correct 245 ms 8976 KB Output is correct
24 Correct 381 ms 8896 KB Output is correct
25 Correct 101 ms 8760 KB Output is correct
26 Correct 118 ms 8792 KB Output is correct
27 Execution timed out 2515 ms 13296 KB Time limit exceeded
28 Halted 0 ms 0 KB -