Submission #683242

#	Time	Username	Problem	Language	Result	Execution time	Memory
683242		Nursik	Swapping Cities (APIO20_swap)	C++14	100 / 100	468 ms	133164 KiB

swap

#include "swap.h"

#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

const int maxn = 3e6 + 200;

int n, m;
int timer, p[maxn], sz[maxn], is[maxn], lst[maxn], deg[maxn], tin[maxn], tout[maxn], up[20][maxn], ans[maxn];
vector<pair<int, pair<int, int>>> kektor;
vector<int> g[maxn];
int get(int v){
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}
bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
    if (upper(a, b))
        return a;
    if (upper(b, a))
        return b;
    for (int i = 19; i >= 0; --i){
        if (up[i][a] > 0 && !upper(up[i][a], b)){
            a = up[i][a];
        }
    }
    return up[0][a];
}
void dfs(int v, int par, int last){
    up[0][v] = par, tin[v] = ++timer;
    for (int i = 1; i <= 19; ++i){
        if (up[i - 1][v] == -1){
            up[i][v] = -1;
            continue;
        }
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    if (is[v] > 0 && v >= n){
        last = v;
    }
   // cout << "st\n";
   // cout << v << " " << last << '\n';
    ans[v] = last;
    for (auto to : g[v]){
        if (to != par){
            dfs(to, v, last);
        }
    }
    tout[v] = ++timer;
}
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){
        int x = u[i], y = v[i];
        kektor.pb(mp(w[i], mp(x, y)));
    }
    sort(kektor.begin(), kektor.end());
    for (int i = 0; i < n + m; ++i){
        p[i] = i, sz[i] = 1, is[i] = 0;
    }
    int uk = n;
    for (int i = 0; i < m; ++i){
        pair<int, pair<int, int>> cur = kektor[i];
        int cost = cur.f, x = cur.s.f, y = cur.s.s;
        int r = get(x), r2 = get(y);
        deg[x] += 1, deg[y] += 1;
        if (r == r2){
            g[uk].pb(r);
            g[r].pb(uk);
            lst[uk] = cost;
            is[uk] |= 1;
            p[r] = uk;
        }
        else{
            g[uk].pb(r);
            g[r].pb(uk);
            g[uk].pb(r2);
            g[r2].pb(uk);
            lst[uk] = cost;
            is[uk] |= (is[r] | is[r2]);
            is[uk] |= (deg[x] >= 3);
            is[uk] |= (deg[y] >= 3);
            p[r] = uk, p[r2] = uk;
        }
        lst[uk] = cost;
        uk += 1;
    }
    dfs(n + m - 1, -1, -1);
}
int getMinimumFuelCapacity(int x, int y) {
    int lc = lca(x, y);
    if (ans[lc] == -1)
        return -1;
   // cout << lc << '\n';
    return lst[ans[lc]];
}

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