Submission #671727

#	Time	Username	Problem	Language	Result	Execution time	Memory
671727		smartmonky	Evacuation plan (IZhO18_plan)	C++14	41 / 100	1147 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()
#define int long long
using namespace std;
 
const int N = 2e6 + 10;
int d[N], ans[N], par[N], sz[N];
vector < pair <int,int> > g[N];
set <int> s[N];
int n;
int dji(int f, int s){
	vector <int> dist(n + 1, -1e9);
	set <pair <int,int> > st;
	st.insert({0, f});
	dist[f] = d[f];
	while (!st.empty()) {
		int v = (--st.end())->second;
		st.erase (--st.end());
		for (size_t j=0; j< g[v].size(); ++j) {
			int to = g[v][j].first;
			if (min(dist[v], d[to]) > dist[to]) {
				st.erase (make_pair (d[to], to));
				if(to == s){
					return  min(dist[v], d[to]);
				}
				dist[to] = min(dist[v], d[to]);
				st.insert (make_pair (d[to], to));
			}
		}
	}
}
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(a != b){
        if(sz[a] < sz[b])
            swap(a,b);
        par[b] = a;
        sz[a] += sz[b];
    }
    if ((int) s[a].size() > (int) s[b].size()) swap(s[a] , s[b]);
 
    for (int x : s[b])
    {
        if (s[a].find(x) != s[a].end())
        {
            ans[x] = w;
            s[a].erase(x);
        }
        else
        {
            s[a].insert(x);
        }
    }
    
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d, 0x3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 1; i <= n; 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]) {
				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;
        for (auto adj : g[u])
        {
            int v = adj.ff;
            if (d[v] >= w) connect(u , v , w);
        }
    }
	for(int i = 1; i <= q; i++)cout << ans[i] << endl;
}

Compilation message (stderr)

plan.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
plan.cpp: In function 'long long int dji(long long int, long long int)':
plan.cpp:17:31: warning: control reaches end of non-void function [-Wreturn-type]
   17 |  vector <int> dist(n + 1, -1e9);
      |                               ^

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