Submission #499354

#	Time	Username	Problem	Language	Result	Execution time	Memory
499354		ismoilov	Evacuation plan (IZhO18_plan)	C++14	100 / 100	662 ms	60476 KiB

plan

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).rbegin(), (x).rend()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
const int maxx = 1e5+5;
vector <pair<int, int>> g[maxx];
set <int> u[maxx];
int d[maxx], s[maxx];
int getp(int x){
	return s[x] == x ? x : s[x] = getp(s[x]);
}
void S()
{
	int n, m;
	cin >> n >> m;
	fp(i,0,n)
		d[i] = INT_MAX;
	fp(i,0,m){
		int x, y, w;
		cin >> x >> y >> w;
		x --, y --;
		g[x].push_back({w, y});
		g[y].push_back({w, x});
	}
	priority_queue <pair<int, int>> q;
	int k;
	cin >> k;
	fp(i,0,k){
		int x;
		cin >> x;
		x --;
		d[x] = 0;
		q.push({-d[x], x});
	}
	while(!q.empty()){
		int c = q.top().first, v = q.top().second;
		q.pop();
		for(auto it : g[v]){
			if(d[v]+it.first < d[it.second])
				d[it.second] = d[v]+it.first, q.push({-d[it.second], it.second});
		}
	}
//	cout << "done\n";
	int t;
	cin >> t;
	vector <int> ans(t);
	vector <pair<int, pair<int, int>>> em;
	fp(i,0,t){
		int x, y;
		cin >> x >> y;
		x --, y --;
		u[x].insert(i);
		u[y].insert(i);
	}
//	cout << "done\n";
	fp(i,0,n){
		s[i] = i;
		for(auto it : g[i])
			em.push_back({min(d[i], d[it.second]), {i, it.second}});
	}
//	cout << "done\n";
	sort(all(em));
//	cout << "done";
	fp(i,0,em.size()){
		int c = em[i].first;
		int x = em[i].second.first, y = em[i].second.second;
	//	cout << x+1 << " " << y+1 << " " << c << "\n";
		x = getp(x);
		y = getp(y);
//		cout << x << " " << y << "\n";
		if(x == y)
			continue;
		if(u[x].size() < u[y].size())
			swap(x, y);
	//	cout << x << " " << y << "\n";
		for(auto it : u[y]){
			if(u[x].count(it)){
				ans[it] = c;
				u[x].erase(it);
			}
			else
				u[x].insert(it);
		}
		s[y] = x;
	}
	for(auto it : ans)
		cout << it << " ";
}
int main()
{
	IOS;
	S();
}

Compilation message (stderr)

plan.cpp: In function 'void S()':
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:21:2: note: in expansion of macro 'fp'
   21 |  fp(i,0,n)
      |  ^~
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:23:2: note: in expansion of macro 'fp'
   23 |  fp(i,0,m){
      |  ^~
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:33:2: note: in expansion of macro 'fp'
   33 |  fp(i,0,k){
      |  ^~
plan.cpp:41:7: warning: unused variable 'c' [-Wunused-variable]
   41 |   int c = q.top().first, v = q.top().second;
      |       ^
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:53:2: note: in expansion of macro 'fp'
   53 |  fp(i,0,t){
      |  ^~
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:61:2: note: in expansion of macro 'fp'
   61 |  fp(i,0,n){
      |  ^~
plan.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
plan.cpp:69:2: note: in expansion of macro 'fp'
   69 |  fp(i,0,em.size()){
      |  ^~
plan.cpp:6:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                                      ~~~~^~~~~
plan.cpp:69:2: note: in expansion of macro 'fp'
   69 |  fp(i,0,em.size()){
      |  ^~

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