제출 #498182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498182		Karliver	자매 도시 (APIO20_swap)	C++17	100 / 100	515 ms	49280 KiB

swap

	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;

const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
const int mxn = 1e5+2;
int n;
VV<PR<int>> g(mxn);
const int G = 20;
int P[mxn][G], F[mxn][G];
bool isfine[mxn];
int R[mxn], S[mxn];
V<AR<int, 3>> E;
V<PR<int>> todo[mxn];
int dep[mxn];
int rt(int x) {
	return R[x]== x ? x : R[x] = rt(R[x]);
}
void add(int x, int y) {
	if(!sz(todo[x]))return;
	for(auto [a, b] : todo[x]) {
		g[a].emplace_back(b,y);
		g[b].emplace_back(a, y);
	}
	todo[x].clear();
}
	
void unite(int a, int b) {
	a = rt(a), b = rt(b);
	if(S[a] < S[b])
		swap(a, b);
	S[a] += S[b];
	isfine[a] |= isfine[b];
	if(sz(todo[a]) > sz(todo[b])) {
		for(auto x : todo[b])
			todo[a].push_back(x);
	}
	else {
		for(auto x : todo[a])
			todo[b].push_back(x);
		swap(todo[a], todo[b]);
	}
	R[b] = a;
}
void dfs(int v, int p, int wei) {
	P[v][0] = p;
	for(int i = 1;i < G;++i) P[v][i] = P[P[v][i-1]][i-1];

	F[v][0] = wei;
	for(int i = 1;i < G;++i) F[v][i] = max(F[v][i-1], F[P[v][i-1]][i-1]);

	for(auto [c, w] : g[v]) {
		if(c == p)continue;
		dep[c] = dep[v]+1;
		dfs(c, v, w);
	}
}
int lca(int a, int b) {
	if(dep[a] < dep[b])
		swap(a, b);
	int k = dep[a]-dep[b];
	
	forn(i, G)if(k >> i & 1) {
		a = P[a][i];
	}
	
	if(a == b)
		return b;
	rforn(i, G) if(P[b][i] != P[a][i]) {
		a = P[a][i];
		b = P[b][i];
	}
	return P[a][0];
}
int get(int x, int k) {
	int mx = 0;
	forn(i, G) if(k >> i & 1) {
		ckma(mx, F[x][i]);
		x = P[x][i];
	}
	return mx;
}
void init(int N, int M, V<int> A, V<int> B, V<int> W) {
	n = N;
	forn(i, M) {
		E.push_back({A[i], B[i], W[i]});
	}
	sort(all(E), [&](AR<int, 3> x, AR<int, 3> y) {return x[2] < y[2];});

	forn(i, N) {
		R[i] = i;
		S[i] = 1;
		isfine[i]= false;
		
	}
	V<int> deg(n);
	for(auto [a, b, c] : E) {
		deg[a]++;
		deg[b]++;
		int ra = rt(a);
		int rb = rt(b);
		if(deg[a] > 2) {
			isfine[ra] = 1;
			add(ra, c);
		}
		if(deg[b] > 2) {
			isfine[rb] = 1;
			add(rb, c);
		}
		if(ra == rb) {
			isfine[ra] = true;
			add(ra, c);
		}
		else {
			unite(a,b);
			int wr = rt(a);
			if(isfine[wr]) {
				add(wr, c);
				g[a].emplace_back(b, c);
				g[b].emplace_back(a, c);
			}
			else
				todo[wr].push_back({a, b});
		}
	}
	
	dfs(0, 0, 0);
}

int getMinimumFuelCapacity(int x, int y) {
	if(!isfine[rt(x)] || (rt(x) != rt(y)))
		return -1;
	int ls = lca(x, y);
	//debug(ls);
	return max(get(x, dep[x]-dep[ls]),get(y, dep[y]-dep[ls]));

}
/*

int main() {

	
	init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
	cout << getMinimumFuelCapacity(1, 2) << '\n';

}*/

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