Submission #202265

#	Time	Username	Problem	Language	Result	Execution time	Memory
202265		ZwariowanyMarcin	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1355 ms	33540 KiB

plan

#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl

using namespace std;

const int nax = 1e5 + 111;
const int INF = 1e9 + 111;

int n, m;
int a, b, c;
vector <pair<int, int>> v[nax];

int k;
vector <int> special;

int q;
int d[nax];
int e[nax];

int L[nax];
int R[nax];
int M[nax];
int G[nax];

int dis[nax];
bool odw[nax];

priority_queue <pair<int, int>> kol;

struct uf {
	int p[nax];
	
	void init() {
		for (int i = 1; i <= n; ++i) p[i] = i;
	}
	
	int find(int x) {
		if (x == p[x]) return x;
		return p[x] = find(p[x]);
	}
	
	void unia(int x, int y) {
		x = find(x);
		y = find(y);
		p[x] = y;
	}
} ja;

vector <pair<int, int>> vec;

vector <pair<int, int>> id;

bool akt[nax];

void solve() {
	ja.init();
	sort(id.begin(), id.end());
	for (int i = 1; i <= n; ++i) akt[i] = 0;
	
	int j = ss(vec) - 1;
	for (int i = ss(id) - 1; 0 <= i; --i) {
		while (0 <= j && id[i].fi <= vec[j].fi) {
			int u = vec[j].se;
			akt[u] = 1;
			for (auto it : v[u]) 
				if (akt[it.fi])
					ja.unia(u, it.fi);
			j--;
		}
		int ID = id[i].se;
		G[ID] = (ja.find(d[ID]) == ja.find(e[ID]));
	}
}	

int main() {		
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d%d", &a, &b, &c);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, c));
	}
	scanf ("%d", &k);
	while (k--) {
		scanf ("%d", &a);
		special.pb(a);
	}
	
	scanf ("%d", &q);
	for (int i = 1; i <= q; ++i) {
		scanf ("%d%d", d + i, e + i);
		L[i] = 0;
		R[i] = INF;
	}
	
	for (int i = 1; i <= n; ++i)
		dis[i] = INF;
	
	for (auto it : special) {
		dis[it] = 0;
		kol.push({0, it});
	}
	
	while (!kol.empty()) {
		int ja = kol.top().se;
		kol.pop();
		if (odw[ja]) continue;
		odw[ja] = 1;
		for (auto it : v[ja]) {
			int d = dis[ja] + it.se;
			if (d < dis[it.fi]) {
				dis[it.fi] = d;
				kol.push({-d, it.fi});
			}
		}
	}
	
	for (int i = 1; i <= n; ++i)
		vec.pb({dis[i], i});
	sort(vec.begin(), vec.end());
	
	for (int i = 1; i <= 32; ++i) {
		id.clear();
		for (int j = 1; j <= q; ++j) {
			M[j] = (L[j] + R[j] + 1) / 2;
			id.pb({M[j], j});
		}
		solve();
		for (int j = 1; j <= q; ++j) {
			if (G[j] == 0)
				R[j] = M[j] - 1;
			else
				L[j] = M[j];
		}
	}
			
	for (int i = 1; i <= q; ++i)
		printf ("%d\n", L[i]);
	
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
plan.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", &a, &b, &c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &k);
  ~~~~~~^~~~~~~~~~
plan.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~
plan.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
plan.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", d + i, e + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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