제출 #950146

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

swap

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 19;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, m, h[N], ok[N], cnt, cnd[N], f[N], par[lg][N], mx[N], deg[N];
int h2[N], p2[lg][N], mx2[lg][N], mx3[lg][N];
vector<pii> alle[N], adj[N], e;
vector<int> tree[N];

int getPar(int v) {return (f[v]==0 ? v : f[v]=getPar(f[v]));}

void merge(int v, int u, int w) {
	if(getPar(v) != getPar(u)) {
		adj[v].pb({u, w});
		adj[u].pb({v, w});
	}
	deg[v]++, deg[u]++; int yey = 0;
	if(max(deg[v], deg[u]) >= 3) yey = 1;
	v=getPar(v), u=getPar(u);
	if(v == u) {
		ok[v] = 1, mx[cnd[v]] = min(mx[cnd[v]], w);
		return;
	}

	tree[cnt].pb(cnd[v]); tree[cnt].pb(cnd[u]);
	ok[v] |= ok[u];
	ok[v] |= yey;
	if(ok[v] == 1) mx[cnt] = w;
	cnd[v] = cnt;
	cnt++;
	f[u] = v;
}

void dfs_init(int v, int p=0) {
	h[v] = h[p] + 1, par[0][v] = (p==0 ? v : p);
	mx[v] = min(mx[v], mx[p]);
	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
	}
	for(auto u : tree[v]) {
		//if(u == p) continue;
		dfs_init(u, v);
	}
}

int getF(int v, int dist) {
	for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {v = par[i][v];}
	return v;
}
int LCA(int v, int u) {
	if(h[v] > h[u]) swap(v, u);
	u = getF(u, h[u]-h[v]);
	if(v == u) return v;
	for(int i=lg-1; i>=0; i--) { if(par[i][v] != par[i][u]) v=par[i][v], u=par[i][u]; }
	return par[0][v];
}

int glob0, glob1;
int getF2(int v, int dist) {
	glob0 = 0, glob1 = 2e9;
	for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {
		glob0 = max(glob0, mx2[i][v]);
		glob1 = min(glob1, mx3[i][v]);
		v = p2[i][v];
	} return v;
}
int LCA2(int v, int u) {
	if(h2[v] > h2[u]) swap(v, u);
	u = getF2(u, h2[u]-h2[v]);
	if(v == u) return v;
	for(int i=lg-1; i>=0; i--) { if(p2[i][v] != p2[i][u]) v=p2[i][v], u=p2[i][u]; }
	return p2[0][v];
}

void dfs2(int v, int p=0) {
	h2[v] = h2[p] + 1, p2[0][v] = p;
	//fuck(mx2[0][v]);
	if(p==0) mx2[0][v] = 2e9;
	for(int i=1; i<lg; i++) {
		p2[i][v] = p2[i-1][p2[i-1][v]];
		mx2[i][v] = max(mx2[i-1][v], mx2[i-1][p2[i-1][v]]);
		mx3[i][v] = min(mx3[i-1][v], mx3[i-1][p2[i-1][v]]);
	}
	for(auto u : adj[v]) {
		if(u.F == p) continue;
		mx2[0][u.F] = u.S;
		dfs2(u.F, v);
	}
}

void init(int _n, int _m, vector<int> V, vector<int> U, vector<int> W) {
	n=_n, m=_m, cnt=_n+1;
	for(int i=0; i<m; i++) {
		V[i]++, U[i]++;
		e.pb({W[i], i});
		alle[V[i]].pb({W[i], U[i]});
		alle[U[i]].pb({W[i], V[i]});
	}
	fill(mx, mx+N, (int)2e9);
	for(int i=0; i<N; i++) cnd[i] = i;
	for(int i=0; i<lg; i++) mx3[i][0] = mx2[i][0] = 2e9;
	for(int i=1; i<=n; i++) {
		sort(all(alle[i]));
		mx3[0][i] = 2e9;
		if(size(alle[i]) >= 3) mx3[0][i] = alle[i][2].F;
	}
	sort(all(e));
	for(auto it : e) {
		merge(V[it.S], U[it.S], it.F);
	}
	dfs2(1);
	dfs_init(cnd[getPar(1)]);
}

int getMinimumFuelCapacity(int v, int u) {
	v++, u++;
	int lca = LCA(v, u), lca2 = LCA2(v, u);
	if(mx[lca]==2e9) return -1;
	int res0=0, res1=2e9;
	//getF2(v, h2[v]-h2[lca2]); res0 = max(res0, glob0), res1 = min(res1, glob1);
	//getF2(u, h2[u]-h2[lca2]); res0 = max(res0, glob0), res1 = min(res1, glob1);
	//res1 = min(res1, mx3[0][lca2]);
	//res0 = max(res0, res1);
	return mx[lca];
}
/*
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)<<endl;
	cout<<getMinimumFuelCapacity(2, 4)<<endl;
	cout<<getMinimumFuelCapacity(0, 1)<<endl;
	init(3, 2, {0, 0}, {1, 2}, {5, 5});
	cout<<getMinimumFuelCapacity(1, 2)<<endl;
	return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:155:23: warning: unused variable 'lca2' [-Wunused-variable]
  155 |  int lca = LCA(v, u), lca2 = LCA2(v, u);
      |                       ^~~~
swap.cpp:157:6: warning: unused variable 'res0' [-Wunused-variable]
  157 |  int res0=0, res1=2e9;
      |      ^~~~
swap.cpp:157:14: warning: unused variable 'res1' [-Wunused-variable]
  157 |  int res0=0, res1=2e9;
      |              ^~~~

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