Submission #379907

#	Time	Username	Problem	Language	Result	Execution time	Memory
379907		nikatamliani	Relay Marathon (NOI20_relaymarathon)	C++14	0 / 100	2731 ms	1048576 KiB

RelayMarathon

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10, M = 1e6+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() && --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: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58