Submission #523775

#	Time	Username	Problem	Language	Result	Execution time	Memory
523775		maomao90	Swapping Cities (APIO20_swap)	C++17	100 / 100	640 ms	65040 KiB

swap

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

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXL 20
#define MAXN 200005

int n, m;
vector<iii> edges;
vii oadj[MAXN], adj[MAXN];
int l[MAXN];
ii p[MAXL][MAXN];
int omn[MAXL][MAXN];

namespace dsu {
    int p[MAXN], rnk[MAXN];
    int findp(int u) {
        if (p[u] == u) return u;
        return p[u] = findp(p[u]);
    }
    bool join(int a, int b) {
        int pa = findp(a), pb = findp(b);
        if (pa == pb) return 0;
        if (rnk[pa] < rnk[pb]) swap(pa, pb);
        if (rnk[pa] == rnk[pb]) rnk[pa]++;
        p[pb] = pa;
        return 1;
    }
}

void dfs(int u) {
    REP (k, 1, MAXL) {
        if (p[k - 1][u].FI == -1) {
            p[k][u] = MP(-1, -1);
        } else {
            p[k][u].FI = p[k - 1][p[k - 1][u].FI].FI;
            p[k][u].SE = max(p[k - 1][u].SE, p[k - 1][p[k - 1][u].FI].SE);
        }
    }
    for (auto [v, w] : adj[u]) {
        if (v == p[0][u].FI) continue;
        l[v] = l[u] + 1;
        p[0][v] = MP(u, w);
        dfs(v);
    }
}

int dp[MAXN], rdp[MAXN], cost[MAXN];
void dfsdp(int u, int p) {
    dp[u] = cost[u] = INF;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfsdp(v, u);
        mnto(dp[u], max(dp[v], w));
    }
    if (oadj[u].size() >= 3) {
        mnto(dp[u], oadj[u][2].SE);
        mnto(cost[u], oadj[u][2].SE);
    }
    REP (i, 0, min((int) oadj[u].size(), 4)) {
        bool die = 0;
        for (auto [v, w] : adj[u]) {
            if (v == oadj[u][i].FI) {
                die = 1;
                break;
            }
        }
        if (!die) {
            mnto(dp[u], oadj[u][i].SE);
            mnto(cost[u], oadj[u][i].SE);
        }
    }
    cerr << u << ": " << dp[u] << "\n";
}

void reroot(int u, int p) {
    vi pre(adj[u].size());
    vi suf(adj[u].size());
    REP (i, 0, adj[u].size()) {
        auto [v, w] = adj[u][i];
        pre[i] = suf[i] = max(dp[v], w);
    }
    REP (i, 1, adj[u].size()) {
        mnto(pre[i], pre[i - 1]);
    }
    RREP (i, adj[u].size() - 2, 0) {
        mnto(suf[i], suf[i + 1]);
    }
    dp[u] = min(suf[0], cost[u]);
    rdp[u] = dp[u];
    cerr << u << ": " << rdp[u] << "\n";
    REP (i, 0, adj[u].size()) {
        auto [v, w] = adj[u][i];
        if (v == p) continue;
        dp[u] = min(cost[u], min(i == 0 ? INF : pre[i - 1],
                i + 1 == adj[u].size() ? INF : suf[i + 1]));
        cerr << " " << u << " " << v << ": " << dp[u] << "\n";
        reroot(v, u);
    }
}

void init(int n, int m, vi u, vi v, vi w) {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    REP (i, 0, n) {
        dsu::p[i] = i;
        dsu::rnk[i] = 0;
    }
    ::n = n; ::m = m;
    REP (i, 0, m) {
        oadj[u[i]].pb(MP(v[i], w[i]));
        oadj[v[i]].pb(MP(u[i], w[i]));
        edges.pb(MT(w[i], u[i], v[i]));
    }
    REP (i, 0, n) {
        sort(ALL(oadj[i]), [&] (ii l, ii r) {
                if (l.SE == r.SE) return l.FI < r.FI;
                return l.SE < r.SE;
                });
    }
    sort(ALL(edges));
    for (auto [w, u, v] : edges) {
        if (dsu::join(u, v)) {
            adj[u].pb(MP(v, w));
            adj[v].pb(MP(u, w));
        }
    }
    p[0][0] = MP(-1, -1);
    dfs(0);
    dfsdp(0, -1);
    reroot(0, -1);
}

// consider other path from x to y
// second mst
int getMinimumFuelCapacity(int x, int y) {
    cerr << x << " " << y << "\n";
    if (l[x] < l[y]) swap(x, y);
    int ox = x, oy = y;
    int cmx = -INF;
    RREP (k, MAXL - 1, 0) {
        if (p[k][x].FI == -1) continue;
        if (l[p[k][x].FI] > l[y]) {
            mxto(cmx, p[k][x].SE);
            x = p[k][x].FI;
            cerr << "jump " << k << " " << x << "\n";
        }
    }
    cerr << " " << x << " " << y << "\n";
    if (p[0][x].FI == y) {
        mxto(cmx, p[0][x].SE);
        x = p[0][x].FI;
    } else {
        if (l[x] != l[y]) {
            mxto(cmx, p[0][x].SE);
            x = p[0][x].FI;
        }
        assert(l[x] == l[y]);
        RREP (k, MAXL - 1, 0) {
            if (p[k][x].FI != p[k][y].FI) {
                mxto(cmx, p[k][x].SE);
                x = p[k][x].FI;

                mxto(cmx, p[k][y].SE);
                y = p[k][y].FI;
            }
        }
        mxto(cmx, p[0][x].SE);
        mxto(cmx, p[0][y].SE);
    }
    mxto(cmx, rdp[ox]);
    if (cmx >= INF) {
        return -1;
    }
    return cmx;
}

/*
10 9
0 1 9
0 2 8
0 3 4
0 4 5
0 5 3
0 6 1
0 7 8
0 8 4
0 9 6
10
0 8
0 5
3 9
2 4
1 7
6 8
1 2
5 6
3 4
5 6
*/

Compilation message (stderr)

swap.cpp: In function 'void reroot(int, int)':
swap.cpp:9:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  106 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
swap.cpp:106:5: note: in expansion of macro 'REP'
  106 |     REP (i, 0, adj[u].size()) {
      |     ^~~
swap.cpp:9:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  110 |     REP (i, 1, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
swap.cpp:110:5: note: in expansion of macro 'REP'
  110 |     REP (i, 1, adj[u].size()) {
      |     ^~~
swap.cpp:9:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  119 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
swap.cpp:119:5: note: in expansion of macro 'REP'
  119 |     REP (i, 0, adj[u].size()) {
      |     ^~~
swap.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 i + 1 == adj[u].size() ? INF : suf[i + 1]));
      |                 ~~~~~~^~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:167:17: warning: unused variable 'oy' [-Wunused-variable]
  167 |     int ox = x, oy = y;
      |                 ^~

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