Submission #671724

#	Time	Username	Problem	Language	Result	Execution time	Memory
671724		smartmonky	Evacuation plan (IZhO18_plan)	C++14	41 / 100	1502 ms	524288 KiB

plan

#include <bits/stdc++.h>
  
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
const int N = 1e6 + 10;
int d[N], ans[N], par[N], sz[N];
vector < pair <int,int> > g[N];
set <int> s[N];
int n;
int vis[N];
int find(int a){
    if(par[a] == a)
        return a;
    return par[a] = find(par[a]);
}
void connect(int a, int b, int w){
    a = find(a);
    b = find(b);
    if(a == b)return;
    if ((int) s[a].size() > (int) s[b].size()) swap(s[a] , s[b]);
	par[b] = a;

    for (auto x : s[b])
    {
        if (s[a].find(x) != s[a].end())
        {
            ans[x] = w;
            s[a].erase(x);
        }
        else
        {
            s[a].insert(x);
        }
    }
}
main(){
	memset(d, 0x3f3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 1; i <= n * 6; i++){
		par[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	int k;
	cin >> k;
	set <pair <int,int> > st;
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		st.insert({0, a});
		d[a] = 0;
	}
	while (!st.empty()){
		int v = st.begin()->second;
		st.erase (st.begin());
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				st.erase (make_pair (d[to], to));
				d[to] = d[v] + len;
				st.insert (make_pair (d[to], to));
			}
		}
	}
	vector <pair <int,int> > vp;
	for(int i = 1; i <= n; i++){
		vp.pb({d[i], i});
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++){
		int a, b;
		cin >> a >> b;
		s[a].insert(i);
		s[b].insert(i);
	}
	sort(rall(vp));
	for (auto x : vp){
        int w = x.first , u = x.second;
        vis[u] = 1;
        for (auto adj : g[u])
        {
            int v = adj.ff;
            if (vis[v]) 
				connect(u , v , w);
        }
    }
	for(int i = 1; i <= q; i++)cout << ans[i] << endl;
}

Compilation message (stderr)

plan.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main(){
      | ^~~~

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