Submission #342158

#	Time	Username	Problem	Language	Result	Execution time	Memory
342158		David_M	Evacuation plan (IZhO18_plan)	C++14	0 / 100	52 ms	49644 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>>n>>m;
	
	for (int i=1; i<=n; i++)
		dist[i]={INF, i};
	
	for (int i=1; i<=m; i++)
		scanf("%d%d%d", x, y, z),
		v[x].pb({y, z}),
		v[y].pb({x, z});
	
	
	cin>>k;
	for (int i=1; i<=k; i++)
		scanf("%d", 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:35:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   35 |   scanf("%d%d%d", x, y, z),
      |          ~^       ~
      |           |       |
      |           int*    int
plan.cpp:35:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'int' [-Wformat=]
   35 |   scanf("%d%d%d", x, y, z),
      |            ~^        ~
      |             |        |
      |             int*     int
plan.cpp:35:15: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'int' [-Wformat=]
   35 |   scanf("%d%d%d", x, y, z),
      |              ~^         ~
      |               |         |
      |               int*      int
plan.cpp:42:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   42 |   scanf("%d", x),
      |          ~^   ~
      |           |   |
      |           |   int
      |           int*
plan.cpp:55: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]
   55 |         for (int i=0; i<v[x].size(); i++) {
      |                       ~^~~~~~~~~~~~
plan.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d%d%d", x, y, z),
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d", x),
      |   ~~~~~^~~~~~~~~

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