Submission #213615

#	Time	Username	Problem	Language	Result	Execution time	Memory
213615		someone_aa	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1064 ms	29412 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;

class dsu {
public:
	int uparent[maxn], n;
	int usize[maxn];

	void init(int _n) {
		n = _n;
		for(int i=0;i<=n;i++) {
			uparent[i] = i;
			usize[i] = 1;
		}
	}
	int ufind(int x) {
		while(x != uparent[x]) 
			x = uparent[x];
		return x;
	}
	void unite(int x, int y) {
		x = ufind(x);
		y = ufind(y);

		if(x == y) return;

		if(usize[x] > usize[y]) {
			uparent[y] = x;
			usize[x] += usize[y];
		}
		else {
			uparent[x] = y;
			usize[y] += usize[x];
		}
	}
}D;

int n, m, k, q, sz;
int result[maxn];
int dist[maxn];
bool visited[maxn];
vector<int>v; // NPP indexes
vector<pair<int,int> > g[maxn];
void get_distances() {
	for(int i=0;i<=n;i++) {
		visited[i] = false;
		dist[i] = INT_MAX;
	}

	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for(int i:v) {
		dist[i] = 0;
		pq.push(mp(0, i));
	}

	while(!pq.empty()) {
		int node = pq.top().second;
		int curr = pq.top().first;
		pq.pop();

		if(visited[node]) continue;
		visited[node] = true;

		for(auto i:g[node]) {
			if(!visited[i.first] && dist[i.first] > curr + i.second) {
				dist[i.first] = curr + i.second;
				pq.push(mp(dist[i.first], i.first));
			}
		}
	}
}

int orgval[maxn];
vector<int>indexes[maxn];
map<int, int>cind;
set<int>st;
void preprocess() {
	for(int i=1;i<=n;i++) {
		st.insert(dist[i]);
	}

	int br = 0;
	for(int i:st) {
		cind[i] = br;
		orgval[br] = i;
		br++;
	}
	sz = br;

	for(int i=1;i<=n;i++) {
		indexes[cind[dist[i]]].pb(i);
	}
}

int ql[maxn], qr[maxn];
int qs[maxn], qt[maxn];
bool answ[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	int a, b, c;
	for(int i=0;i<m;i++) {
		cin>>a>>b>>c;
		g[a].pb(mp(b, c));
		g[b].pb(mp(a, c));
	}
	int x;
	cin>>k;
	for(int i=0;i<k;i++) {
		cin>>x;
		v.pb(x);
	}

	get_distances();
	preprocess();

	cin>>q;
	for(int i=1;i<=q;i++) {
		cin>>qs[i]>>qt[i];
		ql[i] = -1, qr[i] = sz;
	}

	for(int d=0;d<20;d++) {
		//cout<<"At level: "<<d<<"\n";
		D.init(n);

		vector<int>qrs[maxn];
		memset(answ,false,sizeof(answ));

		//cout<<"Queries at beginning\n";
		for(int i=1;i<=q;i++) {
			int mid = (ql[i] + qr[i]) / 2;
			if(qr[i] - ql[i] <= 1) {
				result[i] = orgval[ql[i]];
				continue;
			}
			qrs[mid].pb(i);
		}

		for(int j=sz-1;j>=0;j--) {
			for(int i:indexes[j]) {
				for(auto nxt:g[i]) {
					if(dist[i] <= dist[nxt.first]) {
						D.unite(i, nxt.first);
					}
				}
			}

			for(int i:qrs[j]) {
				if(D.ufind(qs[i]) == D.ufind(qt[i])) {
					answ[i] = true;
				}
			}
		}

		for(int i=1;i<=q;i++) {
			if(qr[i] - ql[i] <= 1) continue;

			int mid = (ql[i] + qr[i]) / 2;
			if(answ[i]) {
				ql[i] = mid;
			}
			else {
				qr[i] = mid;
			}
		}
	}

	for(int i=1;i<=q;i++) {
		cout<<result[i]<<"\n";
	}
}

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