Submission #1093166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093166		windowwife	Swapping Cities (APIO20_swap)	C++14	100 / 100	218 ms	78160 KiB

swap

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6 + 2, LG = 20, inf = 1e18;
int n, m, pu, pv, u[maxn], v[maxn], w[maxn], d[maxn], par[maxn], id[maxn], deg[maxn], st[LG][maxn], res[maxn];
bool good[maxn];
vector<int> adj[maxn];
bool cmp (int x, int y)
{
    return w[x] < w[y];
}
int find_set (int u)
{
    if (par[u] < 0) return u;
    return (par[u] = find_set(par[u]));
}
void union_set (int i)
{
    deg[u[id[i]]]++; deg[v[id[i]]]++;
    pu = find_set(u[id[i]]); pv = find_set(v[id[i]]);
    if (pu == pv)
    {
        par[n + i] += par[pu];
        par[pu] = n + i;
        adj[n + i].push_back(pu);
        good[n + i] = true;
    }
    else
    {
        par[n + i] += par[pu];
        par[n + i] += par[pv];
        par[pu] = par[pv] = n + i;
        adj[n + i].push_back(pu);
        adj[n + i].push_back(pv);
        if (deg[u[id[i]]] > 2 || deg[v[id[i]]] > 2 || good[pu] || good[pv]) good[n + i] = true;
    }
}
void dfs (int u, int p)
{
    st[0][u] = p;
    if (good[u]) res[u] = w[id[u - n]];
    else res[u] = res[p];
    for (int v : adj[u])
    {
        d[v] = d[u] + 1;
        dfs(v, u);
    }
}
int lca (int u, int v)
{
    if (d[u] < d[v]) swap(u, v);
    int diff = d[u] - d[v];
    for (int j = LG - 1; j >= 0; j--)
        if ((diff >> j) & 1)
        {
            diff ^= (1 << j);
            u = st[j][u];
        }
    if (u == v) return u;
    for (int j = LG - 1; j >= 0; j--)
        if (st[j][u] != st[j][v])
        {
            u = st[j][u];
            v = st[j][v];
        }
    return st[0][u];
}
void init (int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    n = N; m = M;
    for (int i = 1; i <= n; i++) par[i] = -1;
    for (int i = m; i >= 1; i--)
    {
        u[i] = U[i - 1] + 1;
        v[i] = V[i - 1] + 1;
        w[i] = W[i - 1];
        id[i] = i;
    }
    sort(id + 1, id + m + 1, cmp);
    for (int i = 1; i <= m; i++) union_set(i);
    res[0] = -1;
    dfs(n + m, 0);
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n + m; i++)
            st[j][i] = st[j - 1][st[j - 1][i]];
}
int getMinimumFuelCapacity (int X, int Y)
{
    X++; Y++;
    return res[lca(X, Y)];
}
#ifdef rtgsp
int main() {
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    int N, M, Q;
	cin >> N >> M >> Q;
	vector<int> U(M), V(M), W(M);
	for (int i = 0; i < M; i++) cin >> U[i];
	for (int i = 0; i < M; i++) cin >> V[i];
	for (int i = 0; i < M; i++) cin >> W[i];
	init(N, M, U, V, W);
    while (Q--)
    {
        int X, Y;
        cin >> X >> Y;
        cout << getMinimumFuelCapacity(X, Y) << '\n';
    }
}
#endif

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