oj.uz

Submission #951601

# Submission time Handle Problem Language Result Execution time Memory
951601 2024-03-22T07:18:47 Z Nhoksocqt1 Swapping Cities (APIO20_swap) C++17
50 / 100
 839 ms 86888 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];

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], cntLeaf[MAXN], tmp[MAXN], maxw, nTree, numNode, numEdge;
bool dp[1003][1003], dx[MAXN], hasChild[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;

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

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

    cnt = 0;
    dsu = DisjointSet(numNode);
    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]) - (!hasChild[u]);
            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);
            hasChild[u] = 1;
            /*cout << u << ' ' << v << ": ";
            for (int i = 0; i < numNode; ++i)
                cout << query(version[cnt], 1, numNode, tIn[i], tOut[i]) << ' '; cout << '\n';*/
        }
    }
}

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

            //cout << '\n' << x << ' ' << y << ' ' << w << ' ' << c << ' ' << mid << ' ' << cntLeafc << ' ' << cntLeafx << ' ' << cntLeafy << ' ' << cntLeafInPath << '\n';
            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(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 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 158 ms 67216 KB Output is correct
10 Correct 197 ms 78160 KB Output is correct
11 Correct 178 ms 75608 KB Output is correct
12 Correct 241 ms 81016 KB Output is correct
13 Correct 139 ms 71996 KB Output is correct
14 Correct 156 ms 66708 KB Output is correct
15 Correct 249 ms 81280 KB Output is correct
16 Correct 248 ms 77416 KB Output is correct
17 Correct 241 ms 85164 KB Output is correct
18 Correct 213 ms 77992 KB Output is correct
19 Correct 57 ms 29780 KB Output is correct
20 Correct 227 ms 81608 KB Output is correct
21 Correct 227 ms 78736 KB Output is correct
22 Correct 237 ms 84864 KB Output is correct
23 Correct 181 ms 79016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 735 ms 57488 KB Output is correct
4 Correct 698 ms 59964 KB Output is correct
5 Correct 769 ms 57828 KB Output is correct
6 Correct 717 ms 59884 KB Output is correct
7 Correct 762 ms 59844 KB Output is correct
8 Correct 793 ms 57472 KB Output is correct
9 Correct 839 ms 57540 KB Output is correct
10 Correct 698 ms 57420 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14800 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 4 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 4 ms 14940 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 4 ms 14684 KB Output is correct
20 Correct 4 ms 14952 KB Output is correct
21 Correct 4 ms 14684 KB Output is correct
22 Correct 4 ms 14856 KB Output is correct
23 Correct 5 ms 14688 KB Output is correct
24 Correct 5 ms 14944 KB Output is correct
25 Correct 5 ms 14948 KB Output is correct
26 Correct 5 ms 14940 KB Output is correct
27 Correct 4 ms 14952 KB Output is correct
28 Correct 5 ms 14940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 158 ms 67216 KB Output is correct
11 Correct 197 ms 78160 KB Output is correct
12 Correct 178 ms 75608 KB Output is correct
13 Correct 241 ms 81016 KB Output is correct
14 Correct 139 ms 71996 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14800 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 4 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 4 ms 14684 KB Output is correct
25 Correct 4 ms 14952 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 4 ms 14856 KB Output is correct
28 Correct 5 ms 14688 KB Output is correct
29 Correct 5 ms 14944 KB Output is correct
30 Correct 5 ms 14948 KB Output is correct
31 Correct 5 ms 14940 KB Output is correct
32 Correct 4 ms 14952 KB Output is correct
33 Correct 5 ms 14940 KB Output is correct
34 Correct 16 ms 22116 KB Output is correct
35 Correct 203 ms 80460 KB Output is correct
36 Correct 203 ms 78420 KB Output is correct
37 Correct 210 ms 77100 KB Output is correct
38 Correct 183 ms 74564 KB Output is correct
39 Correct 192 ms 74056 KB Output is correct
40 Correct 159 ms 69620 KB Output is correct
41 Correct 225 ms 79424 KB Output is correct
42 Correct 192 ms 80152 KB Output is correct
43 Correct 136 ms 70760 KB Output is correct
44 Correct 176 ms 77120 KB Output is correct
45 Correct 446 ms 66516 KB Output is correct
46 Correct 463 ms 80136 KB Output is correct
47 Correct 472 ms 74576 KB Output is correct
48 Correct 457 ms 70728 KB Output is correct
49 Correct 66 ms 22164 KB Output is correct
50 Correct 76 ms 22984 KB Output is correct
51 Correct 284 ms 56044 KB Output is correct
52 Correct 501 ms 86888 KB Output is correct
53 Correct 433 ms 79508 KB Output is correct
54 Correct 466 ms 84492 KB Output is correct
55 Correct 362 ms 70020 KB Output is correct
56 Correct 621 ms 76860 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 158 ms 67216 KB Output is correct
10 Correct 197 ms 78160 KB Output is correct
11 Correct 178 ms 75608 KB Output is correct
12 Correct 241 ms 81016 KB Output is correct
13 Correct 139 ms 71996 KB Output is correct
14 Correct 156 ms 66708 KB Output is correct
15 Correct 249 ms 81280 KB Output is correct
16 Correct 248 ms 77416 KB Output is correct
17 Correct 241 ms 85164 KB Output is correct
18 Correct 213 ms 77992 KB Output is correct
19 Correct 735 ms 57488 KB Output is correct
20 Correct 698 ms 59964 KB Output is correct
21 Correct 769 ms 57828 KB Output is correct
22 Correct 717 ms 59884 KB Output is correct
23 Correct 762 ms 59844 KB Output is correct
24 Correct 793 ms 57472 KB Output is correct
25 Correct 839 ms 57540 KB Output is correct
26 Correct 698 ms 57420 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 3 ms 14800 KB Output is correct
29 Correct 3 ms 14684 KB Output is correct
30 Correct 3 ms 14684 KB Output is correct
31 Correct 3 ms 14684 KB Output is correct
32 Correct 4 ms 14684 KB Output is correct
33 Correct 3 ms 14684 KB Output is correct
34 Correct 4 ms 14940 KB Output is correct
35 Correct 3 ms 14684 KB Output is correct
36 Correct 16 ms 22116 KB Output is correct
37 Correct 203 ms 80460 KB Output is correct
38 Correct 203 ms 78420 KB Output is correct
39 Correct 210 ms 77100 KB Output is correct
40 Correct 183 ms 74564 KB Output is correct
41 Correct 192 ms 74056 KB Output is correct
42 Correct 159 ms 69620 KB Output is correct
43 Correct 225 ms 79424 KB Output is correct
44 Correct 192 ms 80152 KB Output is correct
45 Correct 136 ms 70760 KB Output is correct
46 Correct 176 ms 77120 KB Output is correct
47 Correct 25 ms 22752 KB Output is correct
48 Incorrect 694 ms 84012 KB Output isn't correct
49 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 158 ms 67216 KB Output is correct
11 Correct 197 ms 78160 KB Output is correct
12 Correct 178 ms 75608 KB Output is correct
13 Correct 241 ms 81016 KB Output is correct
14 Correct 139 ms 71996 KB Output is correct
15 Correct 156 ms 66708 KB Output is correct
16 Correct 249 ms 81280 KB Output is correct
17 Correct 248 ms 77416 KB Output is correct
18 Correct 241 ms 85164 KB Output is correct
19 Correct 213 ms 77992 KB Output is correct
20 Correct 735 ms 57488 KB Output is correct
21 Correct 698 ms 59964 KB Output is correct
22 Correct 769 ms 57828 KB Output is correct
23 Correct 717 ms 59884 KB Output is correct
24 Correct 762 ms 59844 KB Output is correct
25 Correct 793 ms 57472 KB Output is correct
26 Correct 839 ms 57540 KB Output is correct
27 Correct 698 ms 57420 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Correct 3 ms 14800 KB Output is correct
30 Correct 3 ms 14684 KB Output is correct
31 Correct 3 ms 14684 KB Output is correct
32 Correct 3 ms 14684 KB Output is correct
33 Correct 4 ms 14684 KB Output is correct
34 Correct 3 ms 14684 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 3 ms 14684 KB Output is correct
37 Correct 16 ms 22116 KB Output is correct
38 Correct 203 ms 80460 KB Output is correct
39 Correct 203 ms 78420 KB Output is correct
40 Correct 210 ms 77100 KB Output is correct
41 Correct 183 ms 74564 KB Output is correct
42 Correct 192 ms 74056 KB Output is correct
43 Correct 159 ms 69620 KB Output is correct
44 Correct 225 ms 79424 KB Output is correct
45 Correct 192 ms 80152 KB Output is correct
46 Correct 136 ms 70760 KB Output is correct
47 Correct 176 ms 77120 KB Output is correct
48 Correct 25 ms 22752 KB Output is correct
49 Incorrect 694 ms 84012 KB Output isn't correct
50 Halted 0 ms 0 KB -