Submission #971915

#	Time	Username	Problem	Language	Result	Execution time	Memory
971915		ByeWorld	Evacuation plan (IZhO18_plan)	C++14	100 / 100	3844 ms	97676 KiB

plan

#include <bits/stdc++.h>
#include <random>
#define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e6+10;
const int INF = 2e9+10;
const int LOG = 30;
const int MOD = 1e9+7;

int n, m, K, Q;
vector <pii> adj[MAXN];
vector <int> vec;
int dis[MAXN], val[MAXN];

priority_queue <pii, vector<pii>, greater<pii>> pq;
void dji(){
	for(int i=1; i<=n; i++) val[i] = INF;
	for(auto in : vec){
		val[in] = 0;
		pq.push({0, in});
	}
	while(!pq.empty()){
		int nw = pq.top().se, dist = pq.top().fi;
		pq.pop();
		// cout << nw << " dist\n";
		if(val[nw] < dist) continue;
		for(auto ed : adj[nw]){
			int nx = ed.fi, wei = ed.se;
			if(val[nx] > val[nw]+wei){
				val[nx] = val[nw]+wei;
				pq.push({val[nx],nx});
			}
		}
	}
}

struct dsu {
	int par[MAXN];
	void bd(){
		for(int i=1; i<=n; i++) par[i] = i;
	}
	int f(int x){
		if(par[x] == x) return x;
		return par[x] = f(par[x]);
	}
	bool con(int x, int y){
		return f(x) == f(y);
	}
	void mer(int x, int y){
		x = f(x); y = f(y);
		if(con(x, y)) return;
		par[x] = y;
	}
} DSU;
int ans[MAXN], x[MAXN], y[MAXN];
vector <ipii> solve[MAXN];
vector <pii> seg;

signed main() {
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int x, y, w; cin >> x >> y >> w;
		adj[x].pb({y, w}); adj[y].pb({x, w});
	}
	cin >> K;
	for(int i=1; i<=K; i++){
		int p; cin >> p;
		vec.pb(p);
	}
	dji();
	// for(int i=1; i<=n; i++) cout << val[i] << " \n"[i==n];
	for(int i=1; i<=n; i++) seg.pb({val[i], i});
	sort(seg.rbegin(), seg.rend());

	// for(auto in : seg) cout << in.fi << " ";
	// 	cout << " xx\n";
	cin >> Q;
	for(int i=1; i<=Q; i++){
		cin >> x[i] >> y[i]; // l = 1, r = val[x]
		int l = 1, r = val[x[i]];

		int ll = 0, rr = seg.size()-1, mid=0, cnt=-1;
		while(ll<=rr){
			mid = (ll+rr)/2;
			if(seg[mid].fi <= val[x[i]]){
				cnt = mid; rr = mid-1;
			} else ll = mid+1;
 		}
 		if(cnt==-1) continue;
 		while(cnt+1 < seg.size() && seg[cnt+1].fi==seg[cnt].fi) cnt++;
		solve[cnt/2].pb({i, {cnt, seg.size()-1}});
		// cout << i << ' '<< cnt << ' ' << val[x[i]] << " cnt\n";
	}

	bool done = 0;
	while(!done){
		done = 1;
		DSU.bd();
		for(int i=0; i<seg.size(); i++){
			for(auto ed : adj[seg[i].se]){
				int nx = ed.fi;
				if(val[nx] >= seg[i].fi){
					DSU.mer(seg[i].se, nx);
					// cout << seg[i].se << ' '<< nx << " nx\n";
				}
			}

			vector <ipii> upd;
			for(auto in : solve[i]){
				int idx = in.fi, l = in.se.fi, r = in.se.se;
				int nl = l, nr = r;
				if(DSU.con(x[idx], y[idx])){
					ans[idx] = seg[i].fi;
					nr = i-1;
					if(nl > nr) continue;
					// cout << nl << ' ' << nr << " nlr\n";
					done = 0;
					upd.pb({idx, {nl, nr}});

				} else {
					nl = i+1;
					if(nl > nr) continue;
					done = 0;
					upd.pb({idx, {nl, nr}});

				}
			}
			solve[i].clear();
			for(auto in : upd) solve[(in.se.fi+in.se.se)/2].pb(in);
		}
	}

	for(int i=1; i<=Q; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:101:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    while(cnt+1 < seg.size() && seg[cnt+1].fi==seg[cnt].fi) cnt++;
      |          ~~~~~~^~~~~~~~~~~~
plan.cpp:91:7: warning: unused variable 'l' [-Wunused-variable]
   91 |   int l = 1, r = val[x[i]];
      |       ^
plan.cpp:91:14: warning: unused variable 'r' [-Wunused-variable]
   91 |   int l = 1, r = val[x[i]];
      |              ^
plan.cpp:110:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i=0; i<seg.size(); i++){
      |                ~^~~~~~~~~~~

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