Submission #724202

#	Time	Username	Problem	Language	Result	Execution time	Memory
724202		danikoynov	Swapping Cities (APIO20_swap)	C++14	100 / 100	262 ms	94264 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int v, u, w;

    edge(int _v, int _u, int _w)
    {
        v = _v;
        u = _u;
        w = _w;
    }
};

const int maxn = 4e5 + 10;
const int inf = 1e9 + 10;


int n, m, lead[maxn], rnk[maxn], is_fixed[maxn];


int find_leader(int v)
{
    if (v == lead[v])
        return v;
    return (lead[v] = find_leader(lead[v]));
}

vector < int > g[maxn];
int vertex_cnt, cost[maxn], deg[maxn];
void unite(int v, int u, int w)
{
    deg[v] ++;
    deg[u] ++;
    bool deg_v = (deg[v] > 2), deg_u = (deg[u] > 2);
    v = find_leader(v);
    u = find_leader(u);
    int cur = ++ vertex_cnt;
    lead[cur] = cur;
    cost[cur] = w;
    if (v == u)
    {
        lead[v] = cur;
        is_fixed[cur] = 1;
        g[cur].push_back(v);
            //cout << cur << " " << v << endl;
        return;
    }


    is_fixed[cur] = max(is_fixed[v], is_fixed[u]);
    if (deg_v || deg_u)
        is_fixed[cur] = 1;
    lead[v] = lead[u] = cur;
    g[cur].push_back(v);
    g[cur].push_back(u);
    //cout << cur << " " << v << endl;
    //cout << cur << " " << u << endl;
}

bool cmp(edge e1, edge e2)
{
    return e1.w < e2.w;
}
vector < edge > edges;

const int maxlog = 22;
int par[maxn], jump[maxn], timer, lvl[maxn];
int tin[maxn], fs[2 * maxn], lg[2 * maxn], dp[maxlog][2 * maxn];
void dfs(int v)
{
    ///cout << v << " : " << is_fixed[v] << endl;
    if (is_fixed[v])
        jump[v] = v;
    else
        jump[v] = jump[par[v]];
    fs[++ timer] = v;
    tin[v] = timer;
    for (int u : g[v])
    {
        lvl[u] = lvl[v] + 1;
        par[u] = v;
        dfs(u);
        fs[++ timer] = v;
    }
}

void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = fs[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= (timer - (1 << j) + 1); i ++)
    {
        dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
        if (lvl[dp[j - 1][i]] < lvl[dp[j][i]])
            dp[j][i] = dp[j - 1][i];
    }

}

int query_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1, ans = dp[len][r - (1 << len) + 1];
    if (lvl[dp[len][l]] < lvl[ans])
        ans = dp[len][l];
    return ans;
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W)
{
    n = N;
    m = M;
    for (int i = 0; i < m; i ++)
    {
        edges.push_back(edge(U[i], V[i], W[i]));
    }

    for (int i = 0; i < n; i ++)
        lead[i] = i;
    vertex_cnt = n - 1;
    sort(edges.begin(), edges.end(), cmp);
    for (int i = 0; i < edges.size(); i ++)
    {
        unite(edges[i].v, edges[i].u, edges[i].w);
    }

    lvl[vertex_cnt] = 1;
    jump[vertex_cnt + 1] = vertex_cnt + 1;
    par[vertex_cnt] = vertex_cnt + 1;
    dfs(vertex_cnt);
    build_sparse_table();


}



int getMinimumFuelCapacity(int X, int Y)
{
    int lca = query_lca(X, Y);
    lca = jump[lca];
    if (lca == vertex_cnt + 1)
        return -1;
    ///cout << "lca " << lca << endl;
    return cost[lca];
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~

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