Submission #1024812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024812		lovrot	Evacuation plan (IZhO18_plan)	C++17	100 / 100	417 ms	44248 KiB

plan

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

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10; 
const int OO = 1e9;

int n, m;
vector<pii> g[N];

int un[N], siz[N]; // MEM
vector<int> cp[N], q[N];

int ans[N]; // MEM
int qa[N], qb[N]; 

int trazi(int u) { 
	if(un[u] == -1) { 
		return u;
	}
	return un[u] = trazi(un[u]);
}

void unija(int u, int v, int k) { 
	u = trazi(u);
	v = trazi(v);

	if(u == v) {
		return; 
	} else if(siz[u] > siz[v]) {
		swap(u, v);
	}

//	printf("o-o %d %d\n", u, v);

	for(int w : cp[u]) { 
		for(int i : q[w]) { 
			if(ans[i] == -1 && (trazi(qa[i]) == u || trazi(qa[i]) == v) && (trazi(qb[i]) == u || trazi(qb[i]) == v)) { 
				ans[i] = k;
//				printf("ans %d %d\n", i, k);
			}
		}
		cp[v].PB(w);
	}

	un[u] = v;
	siz[v] += siz[u];
}

int d[N], ind[N];
set<pii> s;

void dijkstra(vector<int> &npp) { 
	for(int i = 1; i <= n; ++i) { 
		d[i] = OO;
	}
	for(int i : npp) { 
		d[i] = 0;
	}

	for(int i = 1; i <= n; ++i) { 
		s.insert({d[i], i});
	}

	for(; !s.empty(); ) {
		int u = s.begin()->Y;
		s.erase(s.begin());
		for(pii i : g[u]) { 
			if(d[i.X] > d[u] + i.Y) {
				s.erase({d[i.X], i.X});
				d[i.X] = d[u] + i.Y;
				s.insert({d[i.X], i.X});
			}
		}
	}
}

int main() { 
	memset(ans, -1, sizeof(ans));
	memset(un, -1, sizeof(un));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) { 
		siz[i] = 1;
		ind[i] = i;
		cp[i].PB(i);
	}
	for(int i = 0; i < m; ++i) { 
		int u, v, w; scanf("%d%d%d", &u, &v, &w); 
		g[u].PB({v, w});
		g[v].PB({u, w});
	}

	int k; scanf("%d", &k);
	vector<int> npp;
	for(; k--; ) {
		int u; scanf("%d", &u);
		npp.PB(u);
	}

	scanf("%d", &k);
	for(int i = 0; i < k; ++i) { 
		scanf("%d%d", qa + i, qb + i);
		siz[qa[i]] += 1;
		siz[qb[i]] += 1;
		q[qa[i]].PB(i);
		q[qb[i]].PB(i);
	}

	dijkstra(npp);
	sort(ind + 1, ind + n + 1, [](int a, int b) { return d[a] > d[b]; });

	for(int i = 1; i <= n; ++i) { 
//		printf("%d\n", d[i]);
	}

	for(int i = 1; i <= n; ++i) { 
		int u = ind[i];
//		printf("* %d\n", u);
		for(pii j : g[u]) { 
			int v = j.X;
			if(d[v] >= d[u]) { 
				unija(u, v, d[u]);
			}
		}
	}

	for(int i = 0; i < k; ++i) { 
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:99:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  int k; scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
plan.cpp:107:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   int u; scanf("%d", &u);
      |          ~~~~~^~~~~~~~~~
plan.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
plan.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   scanf("%d%d", qa + i, qb + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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