제출 #92965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92965		Moysenko	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4078 ms	78724 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});
	}
}

bool dfs(int v, int mn, int f){
	used[v] = true;
	if (v == f)
		return true;

	for (auto &u : edg[v])
		if (!used[u] && dist[u] >= mn && dfs(u, mn, f))
			return true;

	return false;
}

int Solve(int v, int u){
	int l = 0, r = min(dist[u], dist[v]) + 1, mid;
	while (l + 1 < r){
		mid = (l + r) / 2;
		memset(used, false, sizeof used);
		if (dfs(v, mid, u))
			l = mid;
		else
			r = mid;
	}

	return l;
}

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