Submission #563715

#	Time	Username	Problem	Language	Result	Execution time	Memory
563715		8e7	Swapping Cities (APIO20_swap)	C++17	37 / 100	2071 ms	12880 KiB

swap

//Challenge: Accepted
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};
struct DSU{
	int par[maxn], deg[maxn];	
	bool mark[maxn];
	pii leaf[maxn];
	void init(int n) {
		for (int i = 0;i < n;i++) par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0}; 
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	void Union(int a, int b) {
		int pa = find(a), pb = find(b);
		deg[a]++, deg[b]++;
		if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) mark[pb] = 1;
		if (deg[a] == 1 && deg[b] == 1) {
			leaf[pb] = {a, b};
		} else {
			if (pa == pb && (leaf[pa] == make_pair(a, b) || leaf[pa] == make_pair(b, a))) mark[pb] = 1;
			if (pa != pb) {
				pii p;
				if (deg[leaf[pa].ff] == 1) p.ff = leaf[pa].ff;
				else p.ff = leaf[pa].ss;
				if (deg[leaf[pb].ff] == 1) p.ss = leaf[pb].ff;
				else p.ss = leaf[pb].ss;
				leaf[pb] = p;
			}
		}
		par[pa] = pb;	
	}
} d;
vector<edge> ed;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	for (int i = 0;i < m;i++) ed.push_back(edge(U[i], V[i], W[i]));
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
}

int getMinimumFuelCapacity(int X, int Y) {
	d.init(n);
	int ret = -1;
	for (int i = 0;i < m;i++) {
		d.Union(ed[i].u, ed[i].v);	
		int v = d.find(X);
		debug(v, d.leaf[v].ff, d.leaf[v].ss);
		if (d.find(X) == d.find(Y) && d.mark[d.find(X)]) {
			ret = ed[i].w;
			break;
		}
	}
	debug();
	return ret;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
swap.cpp:71:3: note: in expansion of macro 'debug'
   71 |   debug(v, d.leaf[v].ff, d.leaf[v].ss);
      |   ^~~~~
swap.cpp:70:7: warning: unused variable 'v' [-Wunused-variable]
   70 |   int v = d.find(X);
      |       ^
swap.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
swap.cpp:77:2: note: in expansion of macro 'debug'
   77 |  debug();
      |  ^~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27