Submission #342153

#	Time	Username	Problem	Language	Result	Execution time	Memory
342153		David_M	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4078 ms	34928 KiB

plan

#include <bits/stdc++.h> 
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=1000006, INF=1e9+2021;
int x, y, z, d, e, o, n, m, Q, i, j, k, mid, ans[N], f[N], l[N], r[N], pa[N], sz[N], w;
vector <pair<int, int> > v[N], md;
pair<int, int> dist[N], a[N];
priority_queue<pair<int, int> > q;

int find(int v) {
    if (v==pa[v]) return v;
    return pa[v]=find(pa[v]);
}
 
void Union(int a, int b) {
    a=find(a);
    b=find(b);
    if (a!=b){
        if (sz[a]<sz[b]) swap(a, b);
        pa[b]=a;
        sz[a]+=sz[b];
    }
}

int main(){ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m;
	
	for (int i=1; i<=n; i++){
		dist[i]={INF, i};
	}
	
	for (int i=1; i<=m; i++)
		cin>>x>>y>>z,
		v[x].pb({y, z}),
		v[y].pb({x, z});
	
	
	cin>>k;
	for (int i=1; i<=k; i++)
		cin>>x, 
		q.push({0, x}),
		dist[x].F=0;
	
	cin>>Q;
	for (int i=1; i<=Q; i++)
		cin>>a[i].F>>a[i].S;
	
	while(!q.empty()){
        x=q.top().S;
        d=q.top().F;
        q.pop();
        if(d!=dist[x].F)continue;
        for (int i=0; i<v[x].size(); i++) {
            y=v[x][i].F;
            z=v[x][i].S;
            if (dist[x].F+z<dist[y].F) {
                dist[y].F=dist[x].F+z;
                q.push({dist[y].F, y});
            }
        }
	}
	sort(dist+1, dist+n+1);
	
//	for (int i=1; i<=n; i++){
//		cout<<"______"<<dist[i].F<<" "<<dist[i].S<<endl;
//	}
	
	for(int i=1; i<=Q; i++)
		l[i]=0, r[i]=INF;
	
	for (int i=1; i<=Q; i++)ans[i]=0;
	
	for (int u=1; u<=35; u++){ 
		md.clear();
		for (int i=1; i<=Q; i++)
			md.pb({l[i]+r[i]>>1, i});
		
		sort(md.begin(), md.end());
		
		for (int i=1; i<=n; i++)
			pa[i]=i, sz[i]=1, f[i]=0;
		
		o=n;
		for (int i=Q-1; i>=0; i--){
			mid=md[i].F;
			x=md[i].S;
			
			while(o&&dist[o].F>=mid){
				f[dist[o].S]=1;
				for (int j=0; j<v[dist[o].S].size(); j++)
					if(f[v[dist[o].S][j].F])
						Union(dist[o].S, v[dist[o].S][j].F);
				o--;
			}
			
			if(find(a[x].F)==find(a[x].S)) ans[x]=mid, l[x]=mid+1;
			else r[x]=mid-1;
		}
	}
	
	for (int i=1; i<=Q; i++)
		cout<<ans[i]<<'\n';
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i=0; i<v[x].size(); i++) {
      |                       ~^~~~~~~~~~~~
plan.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |    md.pb({l[i]+r[i]>>1, i});
      |           ~~~~^~~~~
plan.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int j=0; j<v[dist[o].S].size(); j++)
      |                   ~^~~~~~~~~~~~~~~~~~~~

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