Submission #571110

#	Time	Username	Problem	Language	Result	Execution time	Memory
571110		MadokaMagicaFan	Swapping Cities (APIO20_swap)	C++14	100 / 100	448 ms	68456 KiB

swap

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 1e5;
const int M = 2e5;

struct node{
    int w;
    bool c;
    int p;
    int d;
    vector<int> child;
    int jump[30];
};

node ns[N+M];

int par[N+M];
int deg[N];

int
getpar(int x)
{
    return par[x] = (x == par[x]) ? x : getpar(par[x]);
}

void
dfs(int x, int d)
{
    ns[x].d = d;
    for (int i = 0; i < sz(ns[x].child); ++i) {
        ns[ns[x].child[i]].p = x;
        ns[ns[x].child[i]].d = d+1;
        if (ns[ns[x].child[i]].c) {
            dfs(ns[x].child[i], d+1);
        } else {
            for (auto u : ns[ns[x].child[i]].child){
                ns[x].child.pb(u);
            }
        }
    }
    return;
}


void
init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for (int i = 0; i < n+m; ++i) {
        par[i] = i;
        ns[i].c = 0;
    }

    for (int i = 0; i < n; ++i) {
        ns[i].w = 0;
        ns[i].c = 1;
    }

    vector<pair<int,int>> edg;

    for (int i = 0; i < m; ++i) {
        edg.pb({w[i],i});
    }

    sort(edg.begin(), edg.end());

    int root = 0;
    for (int i = 0; i < m; ++i) {
        int x = edg[i].scn;
        ++deg[u[x]];
        ++deg[v[x]];

        if (getpar(u[x]) == getpar(v[x])) {
            if (ns[getpar(u[x])].c == 0) {
                ns[getpar(u[x])].c = 1;
                ns[getpar(u[x])].w = edg[i].fst;
            }
            continue;
        }

        ns[n+i].w = edg[i].fst;
        ns[n+i].child.pb(getpar(u[x]));
        ns[n+i].child.pb(getpar(v[x]));
        ns[n+i].c = 0;
        root = n+i;
        if (deg[u[x]] > 2 || deg[v[x]] > 2) ns[n+i].c = 1;
        if (ns[getpar(u[x])].c && getpar(u[x]) >= n) ns[n+i].c = 1;
        if (ns[getpar(v[x])].c && getpar(v[x]) >= n) ns[n+i].c = 1;
        par[getpar(u[x])] = n+i;
        par[getpar(v[x])] = n+i;
    }

    ns[root].p = root;

    dfs(root,0);

    for (int i = 0; i < n+m; ++i) {
        ns[i].jump[0] = ns[i].p;
    }

    for (int j = 1; j < 30; ++j) {
        for (int i = 0; i < n+m; ++i) {
            ns[i].jump[j] = ns[ns[i].jump[j-1]].jump[j-1];
        }
    }

    return;
}

int
getMinimumFuelCapacity(int x, int y)
{
    while (ns[x].d > ns[y].d) x = ns[x].jump[31-__builtin_clz(ns[x].d-ns[y].d)];
    while (ns[y].d > ns[x].d) y = ns[y].jump[31-__builtin_clz(ns[y].d-ns[x].d)];
    assert(x!=y);

    while (ns[x].p != ns[y].p) {
        for (int j = 0; j < 30; ++j) {
            if (ns[x].jump[j] == ns[y].jump[j]) {
                x = ns[x].jump[j-1];
                y = ns[y].jump[j-1];
                break;
            }
        }
    }

    x = ns[x].p;
    if (!ns[x].c)
        return -1;
    return ns[x].w;
}

#ifdef ONPC
void
solve()
{
    int n,m ;
    cin >> n >> m;
    vector<int> u(m);
    vector<int> v(m);
    vector<int> 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);

    int q;
    cin >> q;
    while (q--) {
        cin >> n >> m;
        cout << getMinimumFuelCapacity(n,m) << endl;
    }
}

int32_t
main()
{
    /* ios_base::sync_with_stdio(0);cin.tie(0); */
    freopen("in", "r", stdin);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
}
#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