제출 #93064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93064		Moysenko	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4006 ms	76684 KiB

plan

/*ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░ 
▄███▀░◐░░░▌░░░░░░░ 
░░░░▌░░░░░▐░░░░░░░ 
░░░░▐░░░░░▐░░░░░░░ 
░░░░▌░░░░░▐▄▄░░░░░ 
░░░░▌░░░░▄▀▒▒▀▀▀▀▄ 
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ 
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
НАСТРОЙКА НА КРИТЫ ██████████████] 100% СОЧНОСТИ*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <chrono>
#include <ctime>
#include <unordered_set>
#include <random>
  
#define ep emplace_back
#define F first
#define S second
  
using namespace std;
  
typedef long long ll;
typedef long double ld;
const int inf = 1e9 + 7;
mt19937 rd(chrono :: system_clock :: now().time_since_epoch().count());
  
#pragma GCC optimize("unroll-loops") // развернуть цикл
#pragma GCC optimize("Ofast") // скомпилировать с о3
/*
#pragma GCC optimize("no-stack-protector") // что-то со стеком
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") // оптимизации процессора
#pragma GCC optimize("fast-math") // оптимизации сопроцессора
*/
 
const int siz = 1e5 + 10;
vector<pair<int, int> > g[siz];
int dist[siz], n;
vector<int> aes;
set<int> edg[siz];
bool used[siz];
 
void Get_dist(){
	for (int i = 0; i < n; i++)
		dist[i] = inf;
 
	set<pair<int, int> > st;
	for (auto &j : aes)
		st.insert({0, j}), dist[j] = 0;
 
	int v, d;
	while (!st.empty()){
		d = st.begin()->F;
		v = st.begin()->S;
		st.erase(st.begin());
 
		if (dist[v] < d)
			continue;
 
		for (auto &u : g[v])
			if (dist[u.F] > dist[v] + u.S)
				dist[u.F] = dist[v] + u.S, st.insert({dist[u.F], u.F});
	}
}
 
int mni[siz];

int Solve(int s, int f){
	set<pair<int, int> > st;
	fill(mni, mni + n, 0);
	mni[s] = dist[s];
	st.insert({dist[s], s});

	int v, d;
	while (!st.empty()){
		auto it = --st.end();
		v = it->S;
		d = it->F;
		st.erase(it);

		if (mni[v] > d)
			continue;
		if (v == f)
			break;

		for (auto &u : edg[v])
			if (mni[u] < min(dist[u], d))
				mni[u] = min(dist[u], d), st.insert({mni[u], u});
	}

	return mni[f];
}
 
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    int m;
    cin >> n >> m;
    int i, v, u, w;
    for (i = 0; i < m; i++){
    	cin >> v >> u >> w;
    	v--, u--;
    	g[v].ep(u, w);
    	g[u].ep(v, w);
    	edg[v].insert(u);
    	edg[u].insert(v);
    }
 
    int k;
    cin >> k;
    aes.resize(k);
    for (auto &j : aes){
    	cin >> j;
    	j--;
    }
 
    Get_dist();
 
    int q;
    cin >> q;
    while (q--){
    	cin >> v >> u;
    	v--, u--;
 
    	//cout << dist[v] << ' ' << dist[u] << '\n';
 
    	if (edg[v].count(u))
    		cout << min(dist[v], dist[u]) << '\n';
    	else
    		cout << Solve(v, u) << '\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46