Submission #237376

#	Time	Username	Problem	Language	Result	Execution time	Memory
237376		_7_7_	Evacuation plan (IZhO18_plan)	C++14	100 / 100	750 ms	35760 KiB

plan

#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int n, m, q, v, u, w, k, d[N], res[N], p[N], pp[N];
vector < pair < int, pii > > gg[N];
set < pii > Q;
vpii g[N];

bool cmp (int x, int y) {
	return d[x] > d[y];
}

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

void merge (int v, int u, int w) {
	v = get(v), u = get(u);
	if (v == u)
		return;

	if (sz(gg[v]) > sz(gg[u]))
		swap(v, u);

	for (auto x : gg[v]) {
		if (res[x.f] != -1)
			continue;
		int p1 = get(x.s.f), p2 = get(x.s.s);
		if ((p1 == v && p2 == u) || (p1 == u && p2 == v)) {
			res[x.f] = w;
			continue;
		}
		gg[u].pb(x);
	}		

	p[v] = u;
}


main () {
	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d%d", &v, &u, &w);
		g[v].pb({w, u});
		g[u].pb({w, v});
	}

	for (int i = 1; i <= n; ++i)
		d[i] = inf;

	scanf("%d", &k);
	while (k--) {
		scanf("%d", &v);
		d[v] = 0;
		Q.insert({0, v});
	}

	while (sz(Q)) {
		int v = Q.begin()->s;
		Q.erase(Q.begin());
		for (auto x : g[v])
			 if (d[x.s] > d[v] + x.f) {
			 	Q.erase(mp(d[x.s], x.s));
			 	d[x.s] = d[v] + x.f;
			 	Q.insert({d[x.s], x.s});
			 }
	}

	
	memset(res, -1, sizeof(res));
	scanf("%d", &q);

	for (int i = 1; i <= q; ++i) {
		scanf("%d%d", &v, &u);
		gg[v].pb({i, {v, u}});
		gg[u].pb({i, {v, u}});
	}


	for (int i = 1; i <= n; ++i)  
		pp[i] = p[i] = i;


	sort(pp + 1, pp + 1 + n, cmp);	
	for (int i = 1; i <= n; ++i) {
		int v = pp[i];
		for (auto u : g[v])
			if (d[u.s] >= d[v]) 
				merge(v, u.s, d[v]);			
	}

	for (int i = 1; i <= q; ++i)
		printf("%d\n", res[i]);
}

Compilation message (stderr)

plan.cpp:76:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
plan.cpp: In function 'int main()':
plan.cpp:77: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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v, &u, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v);
   ~~~~~^~~~~~~~~~
plan.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
plan.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~

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