Submission #724200

#	Time	Username	Problem	Language	Result	Execution time	Memory
724200		danikoynov	Swapping Cities (APIO20_swap)	C++14	0 / 100	89 ms	19704 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);
        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);
}

vector < edge > edges;
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]));
    }
}



int getMinimumFuelCapacity(int X, int Y)
{

    return -1;
}

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