oj.uz

Submission #983274

# Submission time Handle Problem Language Result Execution time Memory
983274 2024-05-15T09:53:20 Z ZHIRDILBILDIZ Swapping Cities (APIO20_swap) C++14
6 / 100
 557 ms 67392 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 3e5 + 10;
struct edge {
    int from, to, w;
    edge () {}
    edge (int a, int b, int c) {
        from = a,
            to = b,
                w = c;
    }
};
bool cmp (edge e1, edge e2) {
    return e1.w < e2.w;
}
vector<edge> roads;

int SZ;
int kol;
int p[N];
int sz[N];
int st[N];
int ed[N];
int dist[N];
bool cycle[N];
vector<pii> gr[N];

void init_dsu () {
    for (int i = 0; i < N; ++i)
        p[i] = i,
            st[i] = i,
                ed[i] = i;
}
int get (int u) {
    if (u != p[u])
        p[u] = get(p[u]);
    return p[u];
}
void join (int u, int v, int w) {
    // cout << "join " << u << ' ' << v << '\n';
    int u1 = u, v1 = v;
    u = get(u);
    v = get(v);
    if (u == v) {
        ++kol;
        // cout << "add_road " << kol << ' ' << u << ' ' << w << '\n';
        gr[kol].push_back({u, w});
        p[u] = kol;
        cycle[kol] = 1;
        return;
    }
    // cout << "segments, u, v " << u << ' ' << v << ' ' << st[u] << ' ' << ed[u] << ' ' << st[v] << ' ' << ed[v] << '\n';
    ++kol;
    cycle[kol] = (cycle[u] | cycle[v]);
    if ((u1 == st[u] || u1 == ed[u]) && (v1 == st[v] || v1 == ed[v])) {
        set<int> all;
        all.insert(st[u]);
        all.insert(ed[u]);
        all.insert(st[v]);
        all.insert(ed[v]);

        if (st[u] != ed[u])
            all.erase(u1);
        if (st[v] != ed[v])
            all.erase(v1);


        st[kol] = (*all.begin());
        ed[kol] = (*all.rbegin());
    } else {
        cycle[kol] = 1;
    }
    // cout << "add_road " << kol << ' ' << u << ' ' << v << ' ' << w << '\n';
    gr[kol].push_back({u, w});
    gr[kol].push_back({v, w});

    p[u] = kol;
    p[v] = kol;
}

int timer;
int tin[N];
int tout[N];
int lc[N][20];
int mx[N][20];

void dfs(int city, int pr, int ls) {
    // cout << "dfs("<<city<<")\n";
    tin[city] = ++timer;

    lc[city][0] = pr;
    mx[city][0] = ls;

    for (int i = 1; i < 20; ++i) {
        lc[city][i] = lc[lc[city][i - 1]][i - 1];
        mx[city][i] = max(mx[city][i - 1], mx[lc[city][i - 1]][i - 1]);
    }

    for (auto i : gr[city]) {
        dist[i.fi] = dist[city] + 1;
        dfs(i.fi, city, i.se);
    }
    tout[city] = ++timer;
}
bool upper(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int get_on_dist (int u, int x) {
    int abu = 0;
    for (int i = 19; i >= 0; --i)
        if (abu + (1 << i) < x && lc[u][i])
            u = lc[u][i];
    return u;
}
bool check_lca (int u, int v, int lca) {
    // cout << "check_lca u, v, lca = " << u << ' ' << v << ' ' << lca << ' ' << upper(lca, u) << ' ' << upper(lca, v) << '\n';
    if (upper(lca, u) && upper(lca, v))
        return 1;
    return 0;
}
int get_max (int lca, int v) {
    if (lca == v)
        return 0;
    int res = 0;
    for (int i = 19; i >= 0; --i)
        if (lc[v][i] && !upper(lc[v][i], lca)) {
            res = max(res, mx[v][i]);
            v = lc[v][i];
        }
    return max(res, mx[v][0]);
}

void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {

    kol = SZ = n;
    for (int i = 0; i < m; ++i) {
        u[i]++;
        v[i]++;
        edge e(u[i], v[i], w[i]);
        roads.push_back(e);
    }

    init_dsu();
    sort(roads.begin(), roads.end(), cmp);
    for (edge e : roads)
        join(e.from, e.to, e.w);
    // for (int i=1;i<=kol;++i) {
    //     cout<<cycle[i] << ' ';
    // }
    // cout << '\n';

    dfs(kol, 0, 0);

}
int getMinimumFuelCapacity (int u, int v) {
    if (u == v)
        return -1;
    ++u;
    ++v;

    int l = 0, r = kol;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        int lca = get_on_dist(u, mid);
        // cout << "mid, lca = " << l << ' ' << r << ' ' << mid << ' ' << lca << ' ' << check_lca(u, v, lca) << ' ' << cycle[lca] << '\n';
        if (!check_lca(u, v, lca) || !cycle[lca]) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (r == kol)
        return -1;
    int lca = get_on_dist(u, r);
    // cout << "u, v, lca = " << u << ' ' << v << ' ' << lca << '\n';
    return max(get_max(lca, u), get_max(lca, v));
}

// signed main () {
//     // ios_base::sync_with_stdio(0);
//     // cin.tie(0), cout.tie(0);

//     int n, m, q;
//     cin >> n >> m;
//     vector<int> u(m), v(m), w(m);
//     for (int i = 0; i < m; ++i)
//         cin >> u[i] >> v[i] >> w[i];
//     init(n, m, u, v, w);

//     cin >> q;
//     while (q--) {
//         int x, y;
//         cin >> x >> y;
//         cout << getMinimumFuelCapacity(x, y) << '\n';
//     }

//     return 0;
// }
// 5 6
// 0 1 4
// 0 2 4
// 2 1 1
// 2 3 3
// 1 3 2
// 1 4 10
//---------------------------
// 10 9
// 0 1 1
// 0 2 1
// 1 3 1
// 2 4 1
// 4 5 1
// 5 6 1
// 6 7 1
// 7 8 1
// 8 9 1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 4 ms 19800 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 19804 KB Output is correct
6 Correct 4 ms 19800 KB Output is correct
7 Correct 5 ms 19800 KB Output is correct
8 Correct 5 ms 19804 KB Output is correct
9 Correct 99 ms 50636 KB Output is correct
10 Correct 124 ms 58268 KB Output is correct
11 Correct 126 ms 58264 KB Output is correct
12 Correct 129 ms 58692 KB Output is correct
13 Correct 126 ms 60864 KB Output is correct
14 Correct 118 ms 50876 KB Output is correct
15 Correct 331 ms 62292 KB Output is correct
16 Correct 328 ms 62324 KB Output is correct
17 Correct 343 ms 62764 KB Output is correct
18 Correct 333 ms 64948 KB Output is correct
19 Correct 145 ms 31760 KB Output is correct
20 Correct 324 ms 63428 KB Output is correct
21 Correct 324 ms 63988 KB Output is correct
22 Correct 334 ms 64040 KB Output is correct
23 Correct 494 ms 66540 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Incorrect 557 ms 67392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 4 ms 19800 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 19804 KB Output is correct
6 Correct 4 ms 19800 KB Output is correct
7 Correct 5 ms 19800 KB Output is correct
8 Correct 5 ms 19804 KB Output is correct
9 Correct 4 ms 19548 KB Output is correct
10 Incorrect 5 ms 19888 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 4 ms 19544 KB Output is correct
4 Correct 4 ms 19800 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct
6 Correct 6 ms 19804 KB Output is correct
7 Correct 4 ms 19800 KB Output is correct
8 Correct 5 ms 19800 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 99 ms 50636 KB Output is correct
11 Correct 124 ms 58268 KB Output is correct
12 Correct 126 ms 58264 KB Output is correct
13 Correct 129 ms 58692 KB Output is correct
14 Correct 126 ms 60864 KB Output is correct
15 Incorrect 5 ms 19888 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 4 ms 19800 KB Output is correct
4 Correct 4 ms 19804 KB Output is correct
5 Correct 6 ms 19804 KB Output is correct
6 Correct 4 ms 19800 KB Output is correct
7 Correct 5 ms 19800 KB Output is correct
8 Correct 5 ms 19804 KB Output is correct
9 Correct 99 ms 50636 KB Output is correct
10 Correct 124 ms 58268 KB Output is correct
11 Correct 126 ms 58264 KB Output is correct
12 Correct 129 ms 58692 KB Output is correct
13 Correct 126 ms 60864 KB Output is correct
14 Correct 118 ms 50876 KB Output is correct
15 Correct 331 ms 62292 KB Output is correct
16 Correct 328 ms 62324 KB Output is correct
17 Correct 343 ms 62764 KB Output is correct
18 Correct 333 ms 64948 KB Output is correct
19 Incorrect 557 ms 67392 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 4 ms 19544 KB Output is correct
4 Correct 4 ms 19800 KB Output is correct
5 Correct 4 ms 19804 KB Output is correct
6 Correct 6 ms 19804 KB Output is correct
7 Correct 4 ms 19800 KB Output is correct
8 Correct 5 ms 19800 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 99 ms 50636 KB Output is correct
11 Correct 124 ms 58268 KB Output is correct
12 Correct 126 ms 58264 KB Output is correct
13 Correct 129 ms 58692 KB Output is correct
14 Correct 126 ms 60864 KB Output is correct
15 Correct 118 ms 50876 KB Output is correct
16 Correct 331 ms 62292 KB Output is correct
17 Correct 328 ms 62324 KB Output is correct
18 Correct 343 ms 62764 KB Output is correct
19 Correct 333 ms 64948 KB Output is correct
20 Incorrect 557 ms 67392 KB Output isn't correct
21 Halted 0 ms 0 KB -