oj.uz

Submission #379904

# Submission time Handle Problem Language Result Execution time Memory
379904 2021-03-19T16:05:09 Z nikatamliani Relay Marathon (NOI20_relaymarathon) C++14
5 / 100
 755 ms 164668 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10, M = 2e5+10;
const long long oo = 1e18+10;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pair<int, long long>>> edges(n+1);
	for(int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges[u].push_back({v, w});
		edges[v].push_back({u, w});
	}
	priority_queue<vector<long long>> q;
	vector<int> special(k+1);
	vector<bool> is_special(n+1);
	for(int i = 1; i <= k; ++i) {
		cin >> special[i];
		is_special[special[i]] = 1;
		q.push({0, special[i], special[i]});
	}
	vector<vector<long long>> v;
	map<pair<int,int>, bool> seen;
	int op = M;
	while(!q.empty() && (int)v.size() < 2*k && --op) {
		auto t = q.top(); q.pop();
		if(t[1] == t[2] && t[0]) continue;
		if(t[1] != t[2] && is_special[t[1]] && seen.find({t[1], t[2]}) == seen.end()) {
			v.push_back({-t[0], min(t[1], t[2]), max(t[1], t[2])});
			seen[{t[1], t[2]}]; seen[{t[2], t[1]}]; 
		}
		for(auto to : edges[t[1]]) {
			q.push({t[0] - to.second, to.first, t[2]});
		}
	}
	sort(v.begin(), v.end());
	const int BLOCK_SIZE = 500;
	const int BLOCK_COUNT = N / BLOCK_SIZE;
	map<int, int> cnt_one[BLOCK_COUNT];
	map<pair<int,int>, int> cnt_two[BLOCK_COUNT];
	for(int i = 0, block = -1; i < (int)v.size(); ++i) {
		if(i % BLOCK_SIZE == 0) ++block;
		cnt_one[block][v[i][1]]++;
		cnt_one[block][v[i][2]]++;
		cnt_two[block][{v[i][1], v[i][2]}]++;
	}
	long long ans = oo;
	auto update = [&](int x, int y) {
		if(v[x][1] != v[y][1] && v[x][1] != v[y][2] && v[x][2] != v[y][1] && v[x][2] != v[y][2]) {
			ans = min(ans, v[x][0] + v[y][0]);
			return true;
		}
		return false;
	};
	auto check_block = [&](int block, int i) {
		bool found = 0;
		int count = cnt_one[block][v[i][1]] + cnt_one[block][v[i][2]] - cnt_two[block][{v[i][1], v[i][2]}];
		if(count != BLOCK_SIZE) {
			for(int x = block * BLOCK_SIZE; !found && x < (block+1) * BLOCK_SIZE && x < (int)v.size(); ++x) {
				found |= update(i, x);
			}
		}		
		return found;
	};
	for(int i = 0; i < (int)v.size(); ++i) {
		int cur_block = i / BLOCK_SIZE;
		bool found = 0;
		for(int block = 0; !found && block < cur_block; ++block) {
			found = check_block(block, i);
		}
		if(!found) {
			check_block(cur_block, i);
		}
	}
	cout << ans << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 24340 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41480 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 165 ms 20880 KB Output is correct
6 Correct 201 ms 22936 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 76 ms 10652 KB Output is correct
10 Correct 169 ms 21008 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 3 ms 1468 KB Output is correct
14 Correct 166 ms 44644 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 3 ms 1212 KB Output is correct
18 Correct 292 ms 41472 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 6 ms 2084 KB Output is correct
21 Correct 3 ms 1084 KB Output is correct
22 Correct 133 ms 13640 KB Output is correct
23 Correct 755 ms 164668 KB Output is correct
24 Correct 175 ms 27776 KB Output is correct
25 Correct 182 ms 22272 KB Output is correct
26 Correct 243 ms 41344 KB Output is correct
27 Correct 109 ms 11664 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 5 ms 1956 KB Output is correct
30 Correct 8 ms 3108 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 24340 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41480 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 165 ms 20880 KB Output is correct
6 Correct 201 ms 22936 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 76 ms 10652 KB Output is correct
10 Correct 169 ms 21008 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 3 ms 1468 KB Output is correct
14 Correct 166 ms 44644 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 3 ms 1212 KB Output is correct
18 Correct 292 ms 41472 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 6 ms 2084 KB Output is correct
21 Correct 3 ms 1084 KB Output is correct
22 Correct 133 ms 13640 KB Output is correct
23 Correct 755 ms 164668 KB Output is correct
24 Correct 175 ms 27776 KB Output is correct
25 Correct 182 ms 22272 KB Output is correct
26 Correct 243 ms 41344 KB Output is correct
27 Correct 109 ms 11664 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 5 ms 1956 KB Output is correct
30 Correct 8 ms 3108 KB Output is correct
31 Incorrect 157 ms 24704 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 28796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 24340 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41480 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 165 ms 20880 KB Output is correct
6 Correct 201 ms 22936 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 76 ms 10652 KB Output is correct
10 Correct 169 ms 21008 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 3 ms 1468 KB Output is correct
14 Correct 166 ms 44644 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 3 ms 1212 KB Output is correct
18 Correct 292 ms 41472 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 6 ms 2084 KB Output is correct
21 Correct 3 ms 1084 KB Output is correct
22 Correct 133 ms 13640 KB Output is correct
23 Correct 755 ms 164668 KB Output is correct
24 Correct 175 ms 27776 KB Output is correct
25 Correct 182 ms 22272 KB Output is correct
26 Correct 243 ms 41344 KB Output is correct
27 Correct 109 ms 11664 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 5 ms 1956 KB Output is correct
30 Correct 8 ms 3108 KB Output is correct
31 Incorrect 157 ms 24704 KB Output isn't correct
32 Halted 0 ms 0 KB -