oj.uz

Submission #951588

# Submission time Handle Problem Language Result Execution time Memory
951588 2024-03-22T07:06:49 Z Nhoksocqt1 Swapping Cities (APIO20_swap) C++17
13 / 100
 779 ms 85216 KB 
#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;

    public:
        DisjointSet(int _n = 0) {
            lab.assign(_n + 7, -1);
        }

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

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

} dsu;

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

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

ii minw[3];
vector<int> idw;
vector<ii> adj[MAXN];
int version[MAXN], tIn[MAXN], tOut[MAXN], tour[MAXN], depth[MAXN], P[MAXN][17], Pw[MAXN][17];
int deg[MAXN], pa[MAXN], wEdge[MAXN], cntLeaf[MAXN], tmp[MAXN], maxw, nTree, 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 init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W) {
    numNode = _N, numEdge = _M;

    minw[0] = minw[1] = minw[2] = {1e9+7, -1};
    check_sub2 = (numEdge + 1 == numNode);
    for (int i = 0; i < numEdge; ++i) {
        edge[i] = {_U[i], _V[i], _W[i]};
        check_sub2 &= (edge[i].u == 0);
        maxw = max(maxw, edge[i].w);
        ++deg[edge[i].u], ++deg[edge[i].v];

        wEdge[edge[i].v] = edge[i].w;
        if(minw[0].fi > edge[i].w) {
            minw[2] = minw[1], minw[1] = minw[0];
            minw[0] = {edge[i].w, edge[i].v};
        } else
            if(minw[1].fi > edge[i].w) {
                minw[2] = minw[1];
                minw[1] = {edge[i].w, edge[i].v};
            } else
                if(minw[2].fi > edge[i].w) {
                    minw[2] = {edge[i].w, 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);

    int cnt(0);
    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);
        if(dsu.join(u, v)) {
            adj[u].push_back(ii(v, cnt));
            adj[v].push_back(ii(u, cnt));
            idw.push_back(edge[i].w);
            ++cnt;
        }
    }

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

    version[0] = build(1, numNode, tmp);
    dsu = DisjointSet(numNode);

    cnt = 0;
    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]) - (dsu.getSize(u) == 1);
            version[cnt] = update(version[cnt - 1], 1, numNode, tIn[u], 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);
        }
    }
}

int sub2(int x, int y) {
    if(numNode <= 3)
        return -1;

    int res = max(wEdge[x], wEdge[y]), cnt(1 + (x == 0));
    for (int k = 0; k < 3; ++k) {
        if(minw[k].se != x && minw[k].se != y) {
            if(--cnt == 0) {
                res = max(res, minw[k].fi);
                break;
            }
        }
    }

    return res;
}

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 sub4(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(numEdge - 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 cntLeafc = query(version[mid + 1], 1, numNode, tIn[c], tOut[c]);
            int cntLeafx = query(version[mid + 1], 1, numNode, tIn[w], tOut[w]) - cntLeafc;
            int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
            int cntLeafInPath = cntLeafc - cntLeafy;

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

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

    return ans;
}

int getMinimumFuelCapacity(int x, int y) {
    if(check_sub1)
        return (numNode == numEdge) ? maxw : -1;

    /*if(check_sub2)
        return sub2(x, y);*/

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

    return sub4(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;

    _U.resize(_M), _V.resize(_M), _W.resize(_M);
    for (int i = 0; i < _M; ++i) {
        cin >> _U[i] >> _V[i] >> _W[i];
    }

    init(_N, _M, _U, _V, _W);
    for (int t = 0; t < _Q; ++t) {
        int _X, _Y;
        cin >> _X >> _Y;
        cout << "MINIMUM FUEL CAPACITY " << _X << " TO " << _Y << ": " << getMinimumFuelCapacity(_X, _Y) << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 148 ms 66844 KB Output is correct
10 Correct 197 ms 78420 KB Output is correct
11 Correct 183 ms 77840 KB Output is correct
12 Correct 194 ms 80704 KB Output is correct
13 Correct 142 ms 71752 KB Output is correct
14 Correct 142 ms 66936 KB Output is correct
15 Correct 224 ms 80860 KB Output is correct
16 Correct 223 ms 77316 KB Output is correct
17 Correct 234 ms 85216 KB Output is correct
18 Correct 180 ms 77740 KB Output is correct
19 Correct 53 ms 29780 KB Output is correct
20 Correct 214 ms 81608 KB Output is correct
21 Correct 206 ms 78648 KB Output is correct
22 Correct 249 ms 84688 KB Output is correct
23 Correct 173 ms 78816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 692 ms 57508 KB Output is correct
4 Correct 702 ms 60116 KB Output is correct
5 Correct 719 ms 57980 KB Output is correct
6 Correct 683 ms 59816 KB Output is correct
7 Correct 750 ms 60184 KB Output is correct
8 Correct 691 ms 57488 KB Output is correct
9 Correct 779 ms 60020 KB Output is correct
10 Correct 688 ms 57876 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 16956 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16940 KB Output is correct
13 Correct 8 ms 16728 KB Output is correct
14 Correct 5 ms 16856 KB Output is correct
15 Incorrect 3 ms 16732 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 148 ms 66844 KB Output is correct
11 Correct 197 ms 78420 KB Output is correct
12 Correct 183 ms 77840 KB Output is correct
13 Correct 194 ms 80704 KB Output is correct
14 Correct 142 ms 71752 KB Output is correct
15 Correct 3 ms 16956 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16940 KB Output is correct
18 Correct 8 ms 16728 KB Output is correct
19 Correct 5 ms 16856 KB Output is correct
20 Incorrect 3 ms 16732 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 148 ms 66844 KB Output is correct
10 Correct 197 ms 78420 KB Output is correct
11 Correct 183 ms 77840 KB Output is correct
12 Correct 194 ms 80704 KB Output is correct
13 Correct 142 ms 71752 KB Output is correct
14 Correct 142 ms 66936 KB Output is correct
15 Correct 224 ms 80860 KB Output is correct
16 Correct 223 ms 77316 KB Output is correct
17 Correct 234 ms 85216 KB Output is correct
18 Correct 180 ms 77740 KB Output is correct
19 Correct 692 ms 57508 KB Output is correct
20 Correct 702 ms 60116 KB Output is correct
21 Correct 719 ms 57980 KB Output is correct
22 Correct 683 ms 59816 KB Output is correct
23 Correct 750 ms 60184 KB Output is correct
24 Correct 691 ms 57488 KB Output is correct
25 Correct 779 ms 60020 KB Output is correct
26 Correct 688 ms 57876 KB Output is correct
27 Correct 3 ms 16956 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 3 ms 16940 KB Output is correct
30 Correct 8 ms 16728 KB Output is correct
31 Correct 5 ms 16856 KB Output is correct
32 Incorrect 3 ms 16732 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 148 ms 66844 KB Output is correct
11 Correct 197 ms 78420 KB Output is correct
12 Correct 183 ms 77840 KB Output is correct
13 Correct 194 ms 80704 KB Output is correct
14 Correct 142 ms 71752 KB Output is correct
15 Correct 142 ms 66936 KB Output is correct
16 Correct 224 ms 80860 KB Output is correct
17 Correct 223 ms 77316 KB Output is correct
18 Correct 234 ms 85216 KB Output is correct
19 Correct 180 ms 77740 KB Output is correct
20 Correct 692 ms 57508 KB Output is correct
21 Correct 702 ms 60116 KB Output is correct
22 Correct 719 ms 57980 KB Output is correct
23 Correct 683 ms 59816 KB Output is correct
24 Correct 750 ms 60184 KB Output is correct
25 Correct 691 ms 57488 KB Output is correct
26 Correct 779 ms 60020 KB Output is correct
27 Correct 688 ms 57876 KB Output is correct
28 Correct 3 ms 16956 KB Output is correct
29 Correct 3 ms 16732 KB Output is correct
30 Correct 3 ms 16940 KB Output is correct
31 Correct 8 ms 16728 KB Output is correct
32 Correct 5 ms 16856 KB Output is correct
33 Incorrect 3 ms 16732 KB Output isn't correct
34 Halted 0 ms 0 KB -