Submission #507576

#	Time	Username	Problem	Language	Result	Execution time	Memory
507576		luka1234	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4 ms	588 KiB

plan

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,m,q,rd;
vector<pair<ll,ll> > g[1001];
ll d[1001];
ll p[1001];
ll sz[1001];
pair<ll,ll> que[1001];
vector<pair<ll,ll> > ord; 
pair<ll,ll> saz[1001];
vector<ll> ms[1001];
bool check[1001];
void dijkstra(vector<ll> v){
	set<pair<ll,ll> > s;
	fill(d,d+n+1,1e9);
	for(ll k:v){
		d[k]=0;
		s.insert({0,k});
	}
	while(!s.empty()){
		ll gza=(*s.begin()).ff;
		ll ver=(*s.begin()).ss;
		s.erase(s.begin());
		for(pair<ll,ll> i:g[ver]){
			if(d[ver]+i.ss<d[i.ff]){
			    s.erase({d[i.ff],i.ff});
				d[i.ff]=d[ver]+i.ss;
				s.insert({d[i.ff],i.ff});
			}
		}
	}
}
void make_set(){
	for(ll k=1;k<=n;k++){
		p[k]=k;
		sz[k]=1;
	}
}
ll find_set(ll v){
    if(v==p[v])
       return v;
    return p[v]=find_set(p[v]);
}
void union_sets(ll a,ll b){
    a=find_set(a);
    b=find_set(b);
    if(a!=b){
        if(sz[a]<sz[b])
            swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
    }
}
void dsu(){
	make_set();
	ll v=1;
	for(pair<ll,ll> i:ord){
		for(pair<ll,ll> j:g[i.ss]){
			if(d[j.ff]>=d[i.ss])
			   union_sets(i.ss,j.ff);
		}
		for(ll j:ms[v]){
			ll fi=que[j].ff;
			ll se=que[j].ss;
			if(find_set(fi)==find_set(se)){
				check[j]=1;
			}
			else{
				check[j]=0;
			}
		}
		v++;
	}
}
int main(){
	cin>>n>>m;
	for(ll k=1;k<=m;k++){
		ll x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	cin>>rd;
	vector<ll> tx;
	for(ll k=1;k<=rd;k++){
		ll x;
		cin>>x;
		tx.push_back(x);
	}
	dijkstra(tx);
	for(ll k=1;k<=n;k++){
		ord.push_back({d[k],k});
	}
	sort(ord.begin(),ord.end());
	reverse(ord.begin(),ord.end());
	/*for(ll k=0;k<ord.size();k++)
	    cout<<ord[k].ff<<' '<<ord[k].ss<<"\n";
	cout<<"\n";*/
	cin>>q;
	for(ll k=1;k<=q;k++){
		saz[k].ff=1;
		saz[k].ss=n;
	}
	for(ll k=1;k<=q;k++){
		ll x,y;
		cin>>x>>y;
		que[k].ff=x;
		que[k].ss=y;
	}
	for(ll k=1;k<=20;k++){
		for(ll i=1;i<=n;i++)
		    ms[i].clear();
		fill(check,check+q+1,0);
		for(ll i=1;i<=q;i++){
			ll md=(saz[i].ff+saz[i].ss)/2;
			ms[md].push_back(i);
		}
		dsu();
		for(ll i=1;i<=q;i++){
			ll md=(saz[i].ff+saz[i].ss)/2;
			if(check[i]==1){
				saz[i].ss=md;
			}
			else{
				saz[i].ff=md+1;
			}
		}
	}
	for(ll k=1;k<=q;k++){
		ll ind=saz[k].ff;
		cout<<ord[ind-1].ff<<"\n";
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra(std::vector<long long int>)':
plan.cpp:24:6: warning: unused variable 'gza' [-Wunused-variable]
   24 |   ll gza=(*s.begin()).ff;
      |      ^~~

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