Submission #50848

#	Time	Username	Problem	Language	Result	Execution time	Memory
50848		Nicksechko	Evacuation plan (IZhO18_plan)	C++14	100 / 100	912 ms	83616 KiB

plan

//Solution by Tima
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
using namespace std;    
const int N = int(5e5) + 10, mod = int(1e9)  + 7; 

int n,m,q,k, a[N], p[N], rnk[N], up[N][18], mx[N][18], tin[N], tout[N], timer;

vector <pair<int,int> > g[N];

vector <pair<int,pair<int,int> > > all;

priority_queue <pair<int,int> > pq;

bool was[N], used[N];

int get(int v){
	if(p[v] == v) return v;
	return p[v] = get(p[v]);
}

bool Merge(int a,int b){
    a = get(a);
    b = get(b);
    if(a == b) return 0;
    if(rnk[a] > rnk[b]) swap(a,b);
    rnk[b] += rnk[a];
    p[a] = b;
    return 1;
}

void dfs(int v){
	used[v] = 1;
	tin[v] = ++timer;
	for(auto p : g[v]){
		if(!used[p.f]){
			up[p.f][0] = v;
			mx[p.f][0] = p.s;
			dfs(p.f);
		}
	}
	tout[v] = ++timer;
}

bool ok(int u,int v){
	return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int lca(int u,int v){
	if(ok(u,v)) return u;
	if(ok(v,u)) return v;
	for(int i = 17; i >= 0; i--){
		if(up[v][i] != -1 && !ok(up[v][i], u)) v = up[v][i];
	}
	return up[v][0];
}

int getx(int v,int u){
    if(v == u) return mod;
    int res = mod;
    for(int i = 17; i >= 0; i--){
    	if(up[v][i] != -1 && !ok(up[v][i], u)){
    		res = min(res, mx[v][i]);
    		v = up[v][i];
    	}
    }
    return min(res, mx[v][0]);
}

int get_min(int u,int v){
	int x = lca(u,v);
	return min(getx(u,x), getx(v,x));
}

int main () {
	scanf("%d%d", &n, &m);

	for(int i = 1,x,y,z; i <= m; i++){
		scanf("%d%d%d", &x, &y, &z);
		g[x].pb(mp(y,z));
		g[y].pb(mp(x,z));
		all.pb(mp(z, mp(x,y)));
	}

	scanf("%d", &k);

	for(int i = 1; i <= n; i++){
		a[i] = mod;
	}

	for(int i = 1,x; i <= k; i++){
		scanf("%d", &x);
		a[x] = 0;
		pq.push(mp(0, x));
	}

	while(!pq.empty()){
		int v = (pq.top()).s;
		pq.pop();
		if(was[v]) continue;
		was[v] = 1;
		for(auto p : g[v]){
			if(a[p.f] > a[v] + p.s){
				a[p.f] = a[v] + p.s;
				pq.push(mp(-a[p.f], p.f));
			}
		}
	}

	for(int i = 0; i < all.size(); i++)	{
		all[i].f = min(a[all[i].s.f], a[all[i].s.s]); 
	}
	
	sort(all.begin(), all.end());

	for(int i = 1; i <= n; i++){
		g[i].clear();
		p[i] = i;
		rnk[i] = 1;
	}

	reverse(all.begin(), all.end());

	for(int i = 0,x,y,z; i < all.size(); i++){
		x = all[i].s.f;
		y = all[i].s.s;
		z = all[i].f;
		if(Merge(x,y)){
			g[x].pb(mp(y,z));
			g[y].pb(mp(x,z));	
		}
	}

	memset(up, -1, sizeof(up));

	for(int j = 0; j <= 17; j++){
		for(int i = 1; i <= n; i++){
			mx[i][j] = mod;
		}
	}

	dfs(1);

	for(int j = 1; j <= 17; j++){
	    for(int i = 1; i <= n; i++) if(up[i][j - 1] != -1){
	        up[i][j] = up[up[i][j - 1]][j - 1];
	        mx[i][j] = min(mx[i][j - 1], mx[up[i][j - 1]][j - 1]);
	    }
	}
	scanf("%d", &q);
	int x,y;
	ll ans = 0,res = 0;
	while(q--){
		scanf("%d%d", &x, &y);
		printf("%d\n", get_min(x,y));
	}

return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < all.size(); i++) {
                 ~~^~~~~~~~~~~~
plan.cpp:147:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0,x,y,z; i < all.size(); i++){
                       ~~^~~~~~~~~~~~
plan.cpp:175:5: warning: unused variable 'ans' [-Wunused-variable]
  ll ans = 0,res = 0;
     ^~~
plan.cpp:175:13: warning: unused variable 'res' [-Wunused-variable]
  ll ans = 0,res = 0;
             ^~~
plan.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:173:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
plan.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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