oj.uz

Submission #951607

# Submission time Handle Problem Language Result Execution time Memory
951607 2024-03-22T07:26:10 Z Nhoksocqt1 Swapping Cities (APIO20_swap) C++17
50 / 100
 884 ms 85184 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[100 * 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(sub5(x, y) != sub4(x, y))
        exit(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];
        _U[i] = Random(0, i), _V[i] = i + 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';
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14692 KB Output is correct
4 Correct 3 ms 14844 KB Output is correct
5 Correct 3 ms 14848 KB Output is correct
6 Correct 4 ms 14688 KB Output is correct
7 Correct 3 ms 14688 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 175 ms 67052 KB Output is correct
10 Correct 214 ms 78380 KB Output is correct
11 Correct 179 ms 75804 KB Output is correct
12 Correct 232 ms 80808 KB Output is correct
13 Correct 141 ms 72000 KB Output is correct
14 Correct 145 ms 66768 KB Output is correct
15 Correct 238 ms 81372 KB Output is correct
16 Correct 235 ms 77700 KB Output is correct
17 Correct 243 ms 85132 KB Output is correct
18 Correct 179 ms 77888 KB Output is correct
19 Correct 57 ms 29984 KB Output is correct
20 Correct 255 ms 81916 KB Output is correct
21 Correct 219 ms 79128 KB Output is correct
22 Correct 248 ms 84608 KB Output is correct
23 Correct 199 ms 79268 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 716 ms 57488 KB Output is correct
4 Correct 771 ms 60024 KB Output is correct
5 Correct 815 ms 57984 KB Output is correct
6 Correct 785 ms 59728 KB Output is correct
7 Correct 840 ms 60036 KB Output is correct
8 Correct 829 ms 57460 KB Output is correct
9 Correct 832 ms 57772 KB Output is correct
10 Correct 884 ms 57704 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14692 KB Output is correct
4 Correct 3 ms 14844 KB Output is correct
5 Correct 3 ms 14848 KB Output is correct
6 Correct 4 ms 14688 KB Output is correct
7 Correct 3 ms 14688 KB Output is correct
8 Correct 4 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 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14808 KB Output is correct
14 Correct 3 ms 14680 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 3 ms 14824 KB Output is correct
19 Correct 4 ms 14680 KB Output is correct
20 Correct 4 ms 14940 KB Output is correct
21 Correct 4 ms 14680 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 4 ms 14684 KB Output is correct
24 Correct 5 ms 14888 KB Output is correct
25 Correct 5 ms 14940 KB Output is correct
26 Correct 5 ms 14940 KB Output is correct
27 Correct 4 ms 14884 KB Output is correct
28 Correct 4 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 2 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14692 KB Output is correct
5 Correct 3 ms 14844 KB Output is correct
6 Correct 3 ms 14848 KB Output is correct
7 Correct 4 ms 14688 KB Output is correct
8 Correct 3 ms 14688 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 175 ms 67052 KB Output is correct
11 Correct 214 ms 78380 KB Output is correct
12 Correct 179 ms 75804 KB Output is correct
13 Correct 232 ms 80808 KB Output is correct
14 Correct 141 ms 72000 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14808 KB Output is correct
19 Correct 3 ms 14680 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14940 KB Output is correct
23 Correct 3 ms 14824 KB Output is correct
24 Correct 4 ms 14680 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 4 ms 14680 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 4 ms 14684 KB Output is correct
29 Correct 5 ms 14888 KB Output is correct
30 Correct 5 ms 14940 KB Output is correct
31 Correct 5 ms 14940 KB Output is correct
32 Correct 4 ms 14884 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct
34 Correct 17 ms 22104 KB Output is correct
35 Correct 228 ms 80096 KB Output is correct
36 Correct 210 ms 77848 KB Output is correct
37 Correct 209 ms 76280 KB Output is correct
38 Correct 194 ms 73832 KB Output is correct
39 Correct 172 ms 73760 KB Output is correct
40 Correct 200 ms 69104 KB Output is correct
41 Correct 200 ms 78700 KB Output is correct
42 Correct 201 ms 79136 KB Output is correct
43 Correct 144 ms 69956 KB Output is correct
44 Correct 192 ms 76412 KB Output is correct
45 Correct 427 ms 64864 KB Output is correct
46 Correct 439 ms 79552 KB Output is correct
47 Correct 484 ms 73520 KB Output is correct
48 Correct 472 ms 69968 KB Output is correct
49 Correct 65 ms 20752 KB Output is correct
50 Correct 75 ms 21848 KB Output is correct
51 Correct 286 ms 55016 KB Output is correct
52 Correct 565 ms 85184 KB Output is correct
53 Correct 495 ms 78036 KB Output is correct
54 Correct 447 ms 82444 KB Output is correct
55 Correct 379 ms 69288 KB Output is correct
56 Correct 645 ms 75284 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14692 KB Output is correct
4 Correct 3 ms 14844 KB Output is correct
5 Correct 3 ms 14848 KB Output is correct
6 Correct 4 ms 14688 KB Output is correct
7 Correct 3 ms 14688 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 175 ms 67052 KB Output is correct
10 Correct 214 ms 78380 KB Output is correct
11 Correct 179 ms 75804 KB Output is correct
12 Correct 232 ms 80808 KB Output is correct
13 Correct 141 ms 72000 KB Output is correct
14 Correct 145 ms 66768 KB Output is correct
15 Correct 238 ms 81372 KB Output is correct
16 Correct 235 ms 77700 KB Output is correct
17 Correct 243 ms 85132 KB Output is correct
18 Correct 179 ms 77888 KB Output is correct
19 Correct 716 ms 57488 KB Output is correct
20 Correct 771 ms 60024 KB Output is correct
21 Correct 815 ms 57984 KB Output is correct
22 Correct 785 ms 59728 KB Output is correct
23 Correct 840 ms 60036 KB Output is correct
24 Correct 829 ms 57460 KB Output is correct
25 Correct 832 ms 57772 KB Output is correct
26 Correct 884 ms 57704 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Correct 3 ms 14684 KB Output is correct
30 Correct 3 ms 14808 KB Output is correct
31 Correct 3 ms 14680 KB Output is correct
32 Correct 3 ms 14684 KB Output is correct
33 Correct 3 ms 14684 KB Output is correct
34 Correct 3 ms 14940 KB Output is correct
35 Correct 3 ms 14824 KB Output is correct
36 Correct 17 ms 22104 KB Output is correct
37 Correct 228 ms 80096 KB Output is correct
38 Correct 210 ms 77848 KB Output is correct
39 Correct 209 ms 76280 KB Output is correct
40 Correct 194 ms 73832 KB Output is correct
41 Correct 172 ms 73760 KB Output is correct
42 Correct 200 ms 69104 KB Output is correct
43 Correct 200 ms 78700 KB Output is correct
44 Correct 201 ms 79136 KB Output is correct
45 Correct 144 ms 69956 KB Output is correct
46 Correct 192 ms 76412 KB Output is correct
47 Correct 25 ms 22620 KB Output is correct
48 Incorrect 666 ms 82088 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 2 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14692 KB Output is correct
5 Correct 3 ms 14844 KB Output is correct
6 Correct 3 ms 14848 KB Output is correct
7 Correct 4 ms 14688 KB Output is correct
8 Correct 3 ms 14688 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 175 ms 67052 KB Output is correct
11 Correct 214 ms 78380 KB Output is correct
12 Correct 179 ms 75804 KB Output is correct
13 Correct 232 ms 80808 KB Output is correct
14 Correct 141 ms 72000 KB Output is correct
15 Correct 145 ms 66768 KB Output is correct
16 Correct 238 ms 81372 KB Output is correct
17 Correct 235 ms 77700 KB Output is correct
18 Correct 243 ms 85132 KB Output is correct
19 Correct 179 ms 77888 KB Output is correct
20 Correct 716 ms 57488 KB Output is correct
21 Correct 771 ms 60024 KB Output is correct
22 Correct 815 ms 57984 KB Output is correct
23 Correct 785 ms 59728 KB Output is correct
24 Correct 840 ms 60036 KB Output is correct
25 Correct 829 ms 57460 KB Output is correct
26 Correct 832 ms 57772 KB Output is correct
27 Correct 884 ms 57704 KB Output is correct
28 Correct 3 ms 14684 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 14808 KB Output is correct
32 Correct 3 ms 14680 KB Output is correct
33 Correct 3 ms 14684 KB Output is correct
34 Correct 3 ms 14684 KB Output is correct
35 Correct 3 ms 14940 KB Output is correct
36 Correct 3 ms 14824 KB Output is correct
37 Correct 17 ms 22104 KB Output is correct
38 Correct 228 ms 80096 KB Output is correct
39 Correct 210 ms 77848 KB Output is correct
40 Correct 209 ms 76280 KB Output is correct
41 Correct 194 ms 73832 KB Output is correct
42 Correct 172 ms 73760 KB Output is correct
43 Correct 200 ms 69104 KB Output is correct
44 Correct 200 ms 78700 KB Output is correct
45 Correct 201 ms 79136 KB Output is correct
46 Correct 144 ms 69956 KB Output is correct
47 Correct 192 ms 76412 KB Output is correct
48 Correct 25 ms 22620 KB Output is correct
49 Incorrect 666 ms 82088 KB Output isn't correct
50 Halted 0 ms 0 KB -