oj.uz

Submission #533237

# Submission time Handle Problem Language Result Execution time Memory
533237 2022-03-05T07:28:29 Z rk42745417 None (JOI16_ho_t3) C++17
26 / 100
 2500 ms 14484 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);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	dis[1] = 0;
	pq.push({0, 1});
	while(!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if(d > dis[u])
			continue;
		for(const auto &[v, c] : edge[u]) {
			int cost = 1 + (add[c] <= t);
			if(dis[v] > dis[u] + cost) {
				dis[v] = dis[u] + cost;
				pq.push({dis[v], 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:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |    int m = l + r >> 1;
      |            ~~^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 3 ms 4176 KB Output is correct
3 Correct 3 ms 4304 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4176 KB Output is correct
6 Correct 3 ms 4176 KB Output is correct
7 Correct 3 ms 4176 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 3 ms 4176 KB Output is correct
3 Correct 3 ms 4304 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4176 KB Output is correct
6 Correct 3 ms 4176 KB Output is correct
7 Correct 3 ms 4176 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 847 ms 14440 KB Output is correct
10 Correct 635 ms 14484 KB Output is correct
11 Correct 155 ms 13320 KB Output is correct
12 Correct 403 ms 13396 KB Output is correct
13 Correct 360 ms 13512 KB Output is correct
14 Correct 348 ms 13396 KB Output is correct
15 Correct 121 ms 10024 KB Output is correct
16 Correct 221 ms 9092 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2574 ms 14420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 3 ms 4176 KB Output is correct
3 Correct 3 ms 4304 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4176 KB Output is correct
6 Correct 3 ms 4176 KB Output is correct
7 Correct 3 ms 4176 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 847 ms 14440 KB Output is correct
10 Correct 635 ms 14484 KB Output is correct
11 Correct 155 ms 13320 KB Output is correct
12 Correct 403 ms 13396 KB Output is correct
13 Correct 360 ms 13512 KB Output is correct
14 Correct 348 ms 13396 KB Output is correct
15 Correct 121 ms 10024 KB Output is correct
16 Correct 221 ms 9092 KB Output is correct
17 Execution timed out 2574 ms 14420 KB Time limit exceeded
18 Halted 0 ms 0 KB -