Submission #507575

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

plan

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

Compilation message (stderr)

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

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