Submission #961872

#	Time	Username	Problem	Language	Result	Execution time	Memory
961872		Nhoksocqt1	Swapping Cities (APIO20_swap)	C++17	100 / 100	1700 ms	145880 KiB

swap

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

class DisjointSet {
    private:
        vector<int> lab, id;

    public:
        DisjointSet(int _n = 0) {
            lab.assign(_n + 7, -1);
            id.resize(_n + 7);
            for (int i = 0; i <= _n; ++i)
                id[i] = i;
        }

        int find(int u) {
            return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
        }

        void updateID(int u, int newID) {
            id[find(u)] = newID;
        }

        bool join(int u, int v) {
            u = find(u), v = find(v);
            if(u == v)
                return (false);

            if(lab[u] > lab[v])
                swap(u, v);

            lab[u] += lab[v];
            lab[v] = u;
            return (true);
        }

        int getSize(int u) {
            return -lab[find(u)];
        }

        int getID(int u) {
            return id[find(u)];
        }

} dsu;

struct Edge {
    int u, v, w;
} edge[2 * MAXN];

struct SegNode {
    int cnt, L, R;
} seg[50 * MAXN];

vector<int> idw;
vector<ii> adj[MAXN], adjp[3 * MAXN];
int depth2[3 * MAXN], nodew[3 * MAXN], fstOk[3 * MAXN], cntNode[3 * MAXN], cntEdge[3 * MAXN], P2[3 * MAXN][19];
int version[MAXN], tIn[MAXN], tOut[MAXN], tour[MAXN], depth[MAXN], P[MAXN][17], Pw[MAXN][17];
int deg[MAXN], pa[MAXN], cntLeaf[MAXN], tmp[MAXN], cntChild[MAXN], maxw, nTree, nNode, numNode, numEdge;
bool dp[1003][1003], dx[MAXN], check_sub1, check_sub2;

int cntTime(0);
void preDfs(int u) {
    tIn[u] = ++cntTime;
    tour[cntTime] = u;

    ++tmp[tIn[u]];
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), id(adj[u][it].se);
        if(v != P[u][0]) {
            depth[v] = depth[u] + 1;
            P[v][0] = u;
            Pw[v][0] = id;
            preDfs(v);
            --tmp[tIn[u]];
        }
    }

    tOut[u] = cntTime;
}

int lca(int u, int v) {
    if(depth[u] < depth[v])
        swap(u, v);

    for (int i1 = depth[u] - depth[v]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        u = P[u][i];
    }

    if(u == v)
        return u;

    for (int i = 31 - __builtin_clz(depth[u]); i >= 0; --i) {
        if(P[u][i] != P[v][i])
            u = P[u][i], v = P[v][i];
    }

    return P[u][0];
}

int build(int l, int r, int tmp[]) {
    if(l == r) {
        seg[++nTree].cnt = tmp[l];
        return nTree;
    }

    int cur(++nTree), mid = (l + r) >> 1;
    seg[cur].L = build(l, mid, tmp);
    seg[cur].R = build(mid + 1, r, tmp);

    seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
    return cur;
}

int update(int oldID, int l, int r, int pos, int val) {
    if(l == r) {
        seg[++nTree] = seg[oldID];
        seg[nTree].cnt += val;
        return nTree;
    }

    int cur(++nTree), mid = (l + r) >> 1;
    seg[cur] = seg[oldID];

    if(pos <= mid) {
        seg[cur].L = update(seg[oldID].L, l, mid, pos, val);
    } else {
        seg[cur].R = update(seg[oldID].R, mid + 1, r, pos, val);
    }

    seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
    return cur;
}

int query(int id, int l, int r, int u, int v) {
    if(u <= l && r <= v)
        return seg[id].cnt;

    int mid = (l + r) >> 1, res(0);
    if(mid >= u)
        res += query(seg[id].L, l, mid, u, v);

    if(mid + 1 <= v)
        res += query(seg[id].R, mid + 1, r, u, v);

    return res;
}

void preDfs2(int u) {
    cntEdge[u] = (u >= numNode);
    cntNode[u] = (u < numNode);
    for (int it = 0; it < sz(adjp[u]); ++it) {
        int v(adjp[u][it].fi), w(adjp[u][it].se);
        nodew[u] = w, P2[v][0] = u;
        depth2[v] = depth2[u] + 1;

        preDfs2(v);
        cntNode[u] += cntNode[v];
        cntEdge[u] += cntEdge[v];
    }
}

void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W) {
    numNode = _N, numEdge = _M;

    for (int i = 0; i < numEdge; ++i) {
        edge[i] = {_U[i], _V[i], _W[i]};
        maxw = max(maxw, edge[i].w);
        ++deg[edge[i].u], ++deg[edge[i].v];
    }

    check_sub1 = 1;
    for (int i = 0; i < numNode; ++i)
        check_sub1 &= (deg[i] <= 2);

    sort(edge, edge + numEdge, [](const Edge &a, const Edge &b) {
        return (a.w < b.w);
    });

    dsu = DisjointSet(numNode);

    nNode = numNode;
    for (int i = 0; i < numNode; ++i)
        cntNode[i] = 1;

    int cnt(0);
    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);

        adjp[nNode].push_back(ii(dsu.getID(u), i));
        if(dsu.find(u) != dsu.find(v)) {
            idw.push_back(edge[i].w);
            adj[u].push_back(ii(v, cnt));
            adj[v].push_back(ii(u, cnt));
            adjp[nNode].push_back(ii(dsu.getID(v), i));
            dsu.join(u, v);
            ++cnt;
        }

        dsu.updateID(u, nNode);
        ++nNode;
    }

    P[0][0] = -1, depth[0] = 1;
    preDfs(0);

    for (int j = 1; (1 << j) <= numNode; ++j) {
        for (int i = 0; i < numNode; ++i) {
            if(P[i][j - 1] == -1) {
                P[i][j] = -1;
            } else {
                P[i][j] = P[P[i][j - 1]][j - 1];
                Pw[i][j] = max(Pw[i][j - 1], Pw[P[i][j - 1]][j - 1]);
            }
        }
    }

    P2[nNode - 1][0] = -1, depth2[nNode - 1] = 1;
    preDfs2(nNode - 1);

    fstOk[nNode - 1] = (cntEdge[nNode - 1] >= cntEdge[nNode - 1]) ? nNode - 1 : -1;
    for (int i = nNode - 2; i >= 0; --i)
        fstOk[i] = (cntEdge[i] >= cntNode[i]) ? i : fstOk[P2[i][0]];

    for (int j = 1; (1 << j) <= nNode; ++j) {
        for (int i = 0; i < nNode; ++i) {
            if(P2[i][j - 1] != -1) {
                P2[i][j] = P2[P2[i][j - 1]][j - 1];
            } else {
                P2[i][j] = -1;
            }
        }
    }

    cnt = 0;
    dsu = DisjointSet(numNode);
    version[0] = build(1, numNode, tmp);
    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);
        if(dsu.find(u) != dsu.find(v)) {
            if(P[u][0] == v)
                swap(u, v);

            ++cnt;
            int qr = query(version[cnt - 1], 1, numNode, tIn[v], tOut[v]) - (++cntChild[u] == 2);
            version[cnt] = update(version[cnt - 1], 1, numNode, tIn[u], qr);
            if(++cntChild[v] == 2) {
                version[cnt] = update(version[cnt], 1, numNode, tIn[v], -1);
                --qr;
            }

            int w(u);
            for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
                if(P[w][i] != -1 && dsu.find(P[w][i]) == dsu.find(u))
                    w = P[w][i];
            }

            w = P[w][0];
            if(w != -1)
                version[cnt] = update(version[cnt], 1, numNode, tIn[w], -qr);

            dsu.join(u, v);
        }
    }

}

ii dfs(int u) {
    dx[u] = 1;
    cntLeaf[u] = 0;
    ii res = {sz(adj[u]), 1};
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi);
        if(!dx[v]) {
            pa[v] = u;
            ii tmp = dfs(v);
            res = {res.fi + tmp.fi, res.se + tmp.se};
            cntLeaf[u] += cntLeaf[v];
        }
    }

    if(cntLeaf[u] == 0)
        cntLeaf[u] = 1;

    return res;
}

int brute(int x, int y) {
    int l(0), r(numEdge - 1), ans(-1);
    while(l <= r) {
        int mid = (l + r) >> 1;

        for (int i = 0; i < numNode; ++i) {
            adj[i].clear();
            dx[i] = 0;
        }

        for (int i = 0; i <= mid; ++i) {
            int u(edge[i].u), v(edge[i].v);
            adj[u].push_back(ii(v, 0));
            adj[v].push_back(ii(u, 0));
        }

        pa[x] = -1;
        ii res = dfs(x);
        bool check(0);
        if(dx[y]) {
            int u(y);
            while(pa[u] != x)
                u = pa[u];

            check = (res.fi / 2 >= res.se || cntLeaf[y] > 1 || cntLeaf[x] - cntLeaf[u] > 1 || cntLeaf[u] - cntLeaf[y] > 0);
        }

        if(check) {
            ans = edge[mid].w;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

int sub5(int x, int y) {
    int l(0), r(numNode - 1), ans(-1);
    int par = lca(x, y);

    int tmp(x);
    for (int i1 = depth[x] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        l = max(l, Pw[tmp][i]);
        tmp = P[tmp][i];
    }

    tmp = y;
    for (int i1 = depth[y] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        l = max(l, Pw[tmp][i]);
        tmp = P[tmp][i];
    }

    if(par == y)
        swap(x, y);

    int c(-1);
    if(par == x) {
        c = y;
        for (int i1 = depth[y] - depth[x] - 1; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1);
            c = P[c][i];
        }
    }

    while(l <= r) {
        int mid = (l + r) >> 1;

        bool check(0);
        if(par == x) {
            int w(x);
            for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
                if(P[w][i] != -1 && Pw[w][i] <= mid)
                    w = P[w][i];
            }

            int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
            if(cntLeafy <= 1) {
                int cntLeafc = query(version[mid + 1], 1, numNode, tIn[c], tOut[c]);
                int cntLeafx = query(version[mid + 1], 1, numNode, tIn[w], tOut[w]) - cntLeafc;
                if(cntLeafx <= 1) {
                    int cntLeafInPath = cntLeafc - cntLeafy;
                    check = (cntLeafInPath > 0);
                } else {
                    check = 1;
                }
            } else {
                check = 1;
            }
        } else {
            if(par > 0 && Pw[par][0] <= mid) {
                check = 1;
            } else {
                int cntLeafx = query(version[mid + 1], 1, numNode, tIn[x], tOut[x]);
                if(cntLeafx <= 1) {
                    int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
                    if(cntLeafy <= 1) {
                        int cntLeafInPath = query(version[mid + 1], 1, numNode, tIn[par], tOut[par]) - cntLeafx - cntLeafy;
                        check = (cntLeafInPath > 0);
                    } else {
                        check = 1;
                    }
                } else {
                    check = 1;
                }
            }
        }

        if(check) {
            ans = idw[mid];
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

int lca2(int u, int v) {
    if(depth2[u] <
        depth2[v])
        swap(u, v);

    for (int i1 = depth2[u] - depth2[v]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        u = P2[u][i];
    }

    if(u == v)
        return u;

    for (int i = 31 - __builtin_clz(depth2[u]); i >= 0; --i) {
        if(P2[u][i] != P2[v][i])
            u = P2[u][i], v = P2[v][i];
    }

    return P2[u][0];
}

int magicFunc(int x, int y) {
    int ansTree = sub5(x, y);
    int p = fstOk[lca2(x, y)];
    int ans = (p < 0) ? -1 : edge[nodew[p]].w;

    if(ansTree < 0 || ans < 0) {
        ans = (ans < 0) ? ansTree : ans;
    } else {
        ans = min(ans, ansTree);
    }

    return ans;
}

int getMinimumFuelCapacity(int x, int y) {
    /*cout << magicFunc(x, y) << ' ' << brute(x, y) << '\n';
    if(magicFunc(x, y) != brute(x, y))
        exit(1);*/

    if(check_sub1)
        return (numNode == numEdge) ? maxw : -1;

    if(numEdge == numNode - 1)
        return sub5(x, y);

    return magicFunc(x, y);
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "swap"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _U, _V, _W;
    int _N, _M, _Q;
    cin >> _N >> _M >> _Q;
    //_N = Random(5e1, 1e2), _M = Random(_N - 1, 2 * _N), _Q = Random(5e4, 2e5); cout << _N << ' ' << _M << ' ' << _Q << '\n';

    _U.resize(_M), _V.resize(_M), _W.resize(_M);
    for (int i = 0; i < _M; ++i) {
        cin >> _U[i] >> _V[i] >> _W[i];
        //if(i < _N - 1) _U[i] = Random(max(0, i - 10), i), _V[i] = i + 1; if(i >= _N - 1) _U[i] = Random(0, _N - 2), _V[i] = Random(_U[i] + 1, _N - 1); _W[i] = Random(1, 1e5); cout << _U[i] << ' ' << _V[i] << ' ' << _W[i] << '\n';
    }

    init(_N, _M, _U, _V, _W);
    for (int t = 0; t < _Q; ++t) {
        int _X, _Y;
        cin >> _X >> _Y;
        //_X = Random(0, _N - 2), _Y = Random(_X + 1, _N - 1);
        cout << "MINIMUM FUEL CAPACITY " << _X << " TO " << _Y << ": " << getMinimumFuelCapacity(_X, _Y) << '\n';
        if(t % 100 == 0)
            cerr << "RUNNING ON QUERY " << t << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:241:44: warning: self-comparison always evaluates to true [-Wtautological-compare]
  241 |     fstOk[nNode - 1] = (cntEdge[nNode - 1] >= cntEdge[nNode - 1]) ? nNode - 1 : -1;
      |                         ~~~~~~~~~~~~~~~~~~ ^~ ~~~~~~~~~~~~~~~~~~

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