oj.uz

Submission #379896

# Submission time Handle Problem Language Result Execution time Memory
379896 2021-03-19T15:56:09 Z nikatamliani Relay Marathon (NOI20_relaymarathon) C++14
5 / 100
 720 ms 164672 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) {
				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 149 ms 24320 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41344 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 150 ms 20880 KB Output is correct
6 Correct 172 ms 23052 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 84 ms 10652 KB Output is correct
10 Correct 174 ms 21156 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 1320 KB Output is correct
14 Correct 147 ms 44664 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 1192 KB Output is correct
18 Correct 289 ms 41344 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 5 ms 2084 KB Output is correct
21 Correct 4 ms 1064 KB Output is correct
22 Correct 133 ms 13584 KB Output is correct
23 Correct 720 ms 164672 KB Output is correct
24 Correct 170 ms 27796 KB Output is correct
25 Correct 180 ms 22256 KB Output is correct
26 Correct 249 ms 41472 KB Output is correct
27 Correct 116 ms 11812 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 4 ms 1956 KB Output is correct
30 Correct 7 ms 3140 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 24320 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41344 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 150 ms 20880 KB Output is correct
6 Correct 172 ms 23052 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 84 ms 10652 KB Output is correct
10 Correct 174 ms 21156 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 1320 KB Output is correct
14 Correct 147 ms 44664 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 1192 KB Output is correct
18 Correct 289 ms 41344 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 5 ms 2084 KB Output is correct
21 Correct 4 ms 1064 KB Output is correct
22 Correct 133 ms 13584 KB Output is correct
23 Correct 720 ms 164672 KB Output is correct
24 Correct 170 ms 27796 KB Output is correct
25 Correct 180 ms 22256 KB Output is correct
26 Correct 249 ms 41472 KB Output is correct
27 Correct 116 ms 11812 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 4 ms 1956 KB Output is correct
30 Correct 7 ms 3140 KB Output is correct
31 Runtime error 178 ms 49940 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 58244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 24320 KB Output is correct
2 Correct 9 ms 3744 KB Output is correct
3 Correct 253 ms 41344 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 150 ms 20880 KB Output is correct
6 Correct 172 ms 23052 KB Output is correct
7 Correct 7 ms 2980 KB Output is correct
8 Correct 24 ms 10652 KB Output is correct
9 Correct 84 ms 10652 KB Output is correct
10 Correct 174 ms 21156 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 1320 KB Output is correct
14 Correct 147 ms 44664 KB Output is correct
15 Correct 4 ms 1704 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 1192 KB Output is correct
18 Correct 289 ms 41344 KB Output is correct
19 Correct 4 ms 1704 KB Output is correct
20 Correct 5 ms 2084 KB Output is correct
21 Correct 4 ms 1064 KB Output is correct
22 Correct 133 ms 13584 KB Output is correct
23 Correct 720 ms 164672 KB Output is correct
24 Correct 170 ms 27796 KB Output is correct
25 Correct 180 ms 22256 KB Output is correct
26 Correct 249 ms 41472 KB Output is correct
27 Correct 116 ms 11812 KB Output is correct
28 Correct 5 ms 2084 KB Output is correct
29 Correct 4 ms 1956 KB Output is correct
30 Correct 7 ms 3140 KB Output is correct
31 Runtime error 178 ms 49940 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -