Submission #571390

#	Time	Username	Problem	Language	Result	Execution time	Memory
571390		BackNoob	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4050 ms	61448 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 24211007;
const ll infll = 1e18 + 7;
const int base = 200;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

vector<pair<int, int>> query[mxN];
ll ans[mxN];

struct DSU{
	vector<int> lab;
	DSU(){}
	DSU(int _n){
		lab.resize(_n + 7, -1);
	}

	int root(int u) {return lab[u] < 0 ? u : root(lab[u]);}

	bool union_root(int u, int v, ll x)
	{
		u = root(u);
		v = root(v);
		if(u == v) return false;
		if(sz(query[u]) < sz(query[v])) swap(u, v);
		for(auto it : query[v]) {
			if(root(it.fi) == u) maximize(ans[it.se], x);
			else query[u].pb(it);
		}
		query[v].clear();
		lab[u] += lab[v];
		lab[v] = u;
		return true;
	}
} dsu;

int n;
int m;
int k;
int q;
bool spec[mxN];
vector<pair<int, int>> adj[mxN];
ll dist[mxN];
pair<ll, int> f[mxN];
bool vis[mxN];

void sp()
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	memset(dist, 0x3f, sizeof(dist));
	for(int i = 1; i <= n; i++) {
		if(spec[i] == true) {
			dist[i] = 0;
			pq.push({dist[i], i});
		}
	}

	while(!pq.empty()) {
		int u = pq.top().se;
		ll cur = pq.top().fi;
		pq.pop();

		if(cur != dist[u]) continue;

		for(auto it : adj[u]) {
			if(minimize(dist[it.fi], cur + it.se) == true) {
				pq.push({dist[it.fi], it.fi});
			}
		}
	}
}

void solve()
{	
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].pb({v, c});
		adj[v].pb({u, c});
	}	

	cin >> k;
	for(int i = 1; i <= k; i++) {
		int u;
		cin >> u;
		spec[u] = true;
	}



	sp();

	cin >> q;
	for(int i = 1; i <= q; i++) {
		int u, v;
		cin >> u >> v;
		query[u].pb({v, i});
		query[v].pb({u, i});
	}

	for(int i = 1; i <= n; i++) f[i] = {dist[i], i};
	sort(f + 1, f + 1 + n);

	// for(int i = 1; i <= n; i++) cout << f[i].fi << ' ' << f[i].se << endl;
	
	memset(ans, -0x3f, sizeof(ans));
	dsu = DSU(n);
	for(int i = n; i >= 1; i--) {
		int j = i;
		while(j > 0 && f[i].fi == f[j].fi) --j;
		for(int k = j + 1; k <= i; k++) vis[f[k].se] = true;
		for(int k = j + 1; k <= i; k++) {
			int u = f[k].se;
			for(auto it : adj[u]) {
				if(vis[it.fi] == true) 
					dsu.union_root(u, it.fi, f[i].fi);
			}
		}
	}

	for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
		
    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

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