Submission #385602

#	Time	Username	Problem	Language	Result	Execution time	Memory
385602		patrikpavic2	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2493 ms	34668 KiB

plan

#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;

set < pii > S;
int dis[N], pos[N];
int q1[N], q2[N], lo[N], hi[N];
int par[N], p[N];
int n, m, q;
vector < pii > v[N];

bool cmp(int A, int B){
	return dis[A] > dis[B];
}

void dijkstra(){
	memset(dis, INF, sizeof(dis));
	for(int i = 1;i <= n;i++){
		if(pos[i]){
			dis[i] = 0; S.insert({0, i});
		}
	}
	for(;!S.empty();S.erase(S.begin())){
		int cur = S.begin() -> Y;
		for(pii nxt : v[cur]){
			if(dis[nxt.X] > dis[cur] + nxt.Y){
				dis[nxt.X] = dis[cur] + nxt.Y;
				S.insert({dis[nxt.X], nxt.X});
			}
		}
	}
}

int pr(int x){
	if(par[x] == x) return x;
	return par[x] = pr(par[x]); 
}

void mrg(int x, int y){
	par[pr(x)] = pr(y);
}

void paralelka(){
	vector < pii > Q;
	for(int i = 0;i < q;i++){
		if(lo[i] != hi[i])
			Q.PB({(lo[i] + hi[i] + 1) / 2, i});
	}
	sort(Q.rbegin(), Q.rend());
	for(int i = 1;i <= n;i++) par[i] = i;
	int j = 0;
	for(int i = 0;i < n;i++){
		while(j < (int)Q.size() && Q[j].X > dis[p[i]]){
			if(pr(q1[Q[j].Y]) == pr(q2[Q[j].Y]))
				lo[Q[j].Y] = Q[j].X;
			else
				hi[Q[j].Y] = Q[j].X - 1;
			j++;
		}
		for(pii pp : v[p[i]])
			if(dis[pp.X] >= dis[p[i]])
				mrg(p[i], pp.X);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0;i < m;i++){
		int x, y, w; scanf("%d%d%d", &x, &y, &w);
		v[x].PB({y, w}), v[y].PB({x, w});
	}
	for(int i = 0;i < n;i++) p[i] = i + 1;
	int k; scanf("%d", &k);
	for(;k--;){
		int x; scanf("%d", &x);
		pos[x] = 1;
	}
	dijkstra();
	sort(p, p + n, cmp);
	scanf("%d", &q);
	for(int i = 0;i < q;i++){
		scanf("%d%d", q1 + i, q2 + i);
		lo[i] = 0;
		hi[i] = INF - 1;	
	}
	for(int i = 0;i < 31;i++) paralelka();
	for(int i = 0;i < q;i++)
		printf("%d\n", lo[i]);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:82:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   int x, y, w; scanf("%d%d%d", &x, &y, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  int k; scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
plan.cpp:88:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~
plan.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
plan.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   scanf("%d%d", q1 + i, q2 + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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