Submission #820294

#	Time	Username	Problem	Language	Result	Execution time	Memory
820294		damwuan	Swapping Cities (APIO20_swap)	C++17	100 / 100	278 ms	65228 KiB

swap

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=4e5+69;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,par[maxn],m,deg[maxn],val[maxn],up[maxn][20],in[maxn],out[maxn],Time,ans[maxn];
bool ok[maxn];
vector<int> adj[maxn];
pair<int,pii> Edge[maxn];
map<pii,int> L;
int Find(int u)
{
    return (par[u]<0?u:par[u]=Find(par[u]));
}
void AddEdge(int u,int v,int w)
{
    val[n]=w;
    deg[u]++;
    deg[v]++;
    if (deg[u]>2 || deg[v]>2) ok[n]=1;
    u=Find(u);
    v=Find(v);
    par[n]+=par[u];
    par[u]=n;
    adj[n].pb(u);
    if (u!=v)
    {
        adj[n].pb(v);
        par[n]+=par[v];
        par[v]=n;
    }
    ok[n]=ok[n]|ok[u]|ok[v];
    //cerr<<n<<' '<<ok[n]<<' '<<val[n]<< " kk\n";
    n++;
}
void dfs(int u,int pre)
{
    in[u]=++Time;
    up[u][0]=pre;
    for1(i,1,19)
    {
        up[u][i]=up[up[u][i-1]][i-1];
    }
    if (ok[u]||adj[u].size()==1) ans[u]=val[u];
    else if (u!=pre) ans[u]=ans[pre];
    else ans[u]=-1;
    //cerr <<"acac "<<u<<' '<<ans[u]<<'\n';
    for(int v: adj[u])
    {
        dfs(v,u);
    }
    out[u]=Time;
}
bool is_ancestor(int u,int v)
{
    return (in[u]<=in[v] && out[v] <= out[u]);
}
int lca(int u,int v)
{
    if (is_ancestor(u,v)) return u;
    if (is_ancestor(v,u)) return v;
    for2(i,19,0)
    {
        if (!is_ancestor(up[u][i],v)) u=up[u][i];
    }
    return up[u][0];
}
void init(int N,int M,vector<int> U,vector<int> V, vector<int> W)
{
    n=N;
    m=M;
    for1(i,0,n+m) par[i]=-1;
    for1(i,0,m-1)
    {
        Edge[i+1]={W[i],{U[i],V[i]}};
        //L[{U[i],V[i]}]=W[i];
    }
    sort(Edge+1,Edge+1+m);
    for1(i,1,m)
    {
        AddEdge(Edge[i].se.fi,Edge[i].se.se,Edge[i].fi);
    }
    dfs(n-1,n-1);
}
int getMinimumFuelCapacity(int X, int Y) {
  return ans[lca(X,Y)];
}

//
//int main() {
//  int N, M;
//  assert(2 == scanf("%d %d", &N, &M));
//
//  std::vector<int> U(M), V(M), W(M);
//  for (int i = 0; i < M; ++i) {
//    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//  }
//
//  int Q;
//  assert(1 == scanf("%d", &Q));
//
//  std::vector<int> X(Q), Y(Q);
//  for (int i = 0; i < Q; ++i) {
//    assert(2 == scanf("%d %d", &X[i], &Y[i]));
//  }
//
//  init(N, M, U, V, W);
//
//  std::vector<int> minimum_fuel_capacities(Q);
//  for (int i = 0; i < Q; ++i) {
//    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
//  }
//
//  for (int i = 0; i < Q; ++i) {
//    printf("%d\n", minimum_fuel_capacities[i]);
//  }
//
//  return 0;
//}

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