Submission #1233076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233076		CELD_07	Swapping Cities (APIO20_swap)	C++20	100 / 100	370 ms	109444 KiB

swap

#include "swap.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) //cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> adj, up;
vector<ll> s, p, v2, dg, v3, v4;
vector<tuple<ll, ll, ll>> v1;
inline ll _find(ll n){
if(p[n]!=n){p[n]=_find(p[n]);return p[n];}
return n;
}
ll cnt=0;
inline void _union(ll a, ll b, ll w){
ll x=a, y=b;
a=_find(a);
b=_find(b);
if(a==b){
adj[cnt].push_back(v3[a]);
adj[v3[a]].push_back(cnt);
dg[x]++;
dg[y]++;
v2[cnt]=1;
v4[cnt]=w;
v3[a]=cnt;
cnt++;
return;
}
adj[cnt].push_back(v3[a]);
adj[v3[a]].push_back(cnt);
adj[cnt].push_back(v3[b]);
adj[v3[b]].push_back(cnt);
dg[x]++;
dg[y]++;
if(dg[x]>=3 || dg[y]>=3)v2[cnt]=1;
if(v2[v3[a]]==1 || v2[v3[b]]==1)v2[cnt]=1;
v4[cnt]=w;
if(s[a]<s[b])swap(a, b);
v3[a]=cnt;
s[a]+=s[b];
p[b]=a;
cnt++;
}
ll n;
vector<ll> dist;
inline void dfs(ll n, ll p, ll res){
up[n][0]=p;
if(v2[n]==1)res=v4[n];
v4[n]=res;
for(int i=1; i<23; i++){
up[n][i]=up[up[n][i-1]][i-1];
}
for(auto y: adj[n]){
if(y==p)continue;
dist[y]=dist[n]+1;
dfs(y, n, res);
}
}
inline ll lca(ll a, ll b){
if(dist[a]<dist[b])swap(a, b);
for(int i=22; i>=0; i--){
if(dist[up[a][i]]>=dist[b])a=up[a][i];
}
if(a==b)return v4[a];
for(int i=22; i>=0; i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return v4[up[a][0]];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<ll>>().swap(adj);
vector<vector<ll>>().swap(up);
vector<ll>().swap(p);
vector<ll>().swap(s);
vector<ll>().swap(dg);
vector<ll>().swap(v4);
vector<ll>().swap(v3);
vector<ll>().swap(dist);
vector<ll>().swap(v2);
n=N;
dist.assign(N+M+10, 0);
up.resize(N+M+10, vector<ll>(23));
v2.assign(n+10+M, 0);
p.resize(n+1);
s.assign(n+1, 1);
dg.assign(n+1, 0);
v3.resize(n+10+M);
v4.resize(n+10+M);
iota(all(p), 0);
iota(all(v3), 0);
adj.resize(N+M+10);
cnt=N;
vector<tuple<ll, ll, ll>>().swap(v1);
for(int i=0; i<M; i++){
v1.push_back({W[i], V[i], U[i]});
}
sort(all(v1));
for(auto& [w, y, x]: v1)_union(x, y, w);
dfs(cnt-1, cnt-1, -1);
}

int getMinimumFuelCapacity(int X, int Y) {
  return lca(X, Y);
}
/*
int main(){
ll a, b, c;
cin>>a>>b;
vector<int> v(b), v1(b), v2(b);
for(int i=0; i<b; i++){
cin>>v[i]>>v1[i]>>v2[i];
}
init(a, b, v, v1, v2);
while(1){
cin>>a>>b;
cout<<getMinimumFuelCapacity(a, b)<<endl;
}
}
*/

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