oj.uz

Submission #1068088

# Submission time Handle Problem Language Result Execution time Memory
1068088 2024-08-21T07:18:11 Z Requiem Swapping Cities (APIO20_swap) C++17
0 / 100
 239 ms 31292 KB 
#include "swap.h"

#include<bits/stdc++.h>
//#define int long long
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
#define TASKNAME "swapcities"
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define se second
#define inf 1e9 + 2
#define fi first
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

/**
Cho đồ thị liên thông n đỉnh m cạnh.
Cạnh i nối 2 đỉnh ui vi có trọng số là wi.

Ta có q truy vấn:
Xi và Yi.

Ta cần tìm 2 đường đi từ Xi đến Yi và từ Yi đến Xi cho 2 xe di chuyển sao cho:
- 2 xe không đến 1 thành phố vào cùng 1 thời điểm
- 2 xe không dược đi theo 2 chiều ngược nhau của cùng 1 cạnh cùng 1 lúc.
- Trọng số của cạnh lớn nhất trên đường đi là nhỏ nhất.
- 1 xe có thể đứng đợi tại 1 thành phố nào đó.

subtask 1: bậc đồ thị 0 quá 2.
Trường hợp 1: Cây đường thẳng thì bỏ qua.
Trường hợp 2: đồ thị vòng thì tôi đơn giản là max các cạnh

subtask 2: đồ thị hình sao.
TH1: u = 0, v != 0 thì tôi sẽ chọn 1 đỉnh khác u nhỏ nhất để trốn.
TH2: u != 0 và v != 0 thì tôi chọn 1 đỉnh khác u và v nhỏ nhất để trốn.

subtask 3, 4: q <= 5, n <= 1000, m <= 1000. Mình đang nghĩ đến chặt nhị phân.
Giả sử mình có 1 cái đồ thị con mà cạnh lớn nhất <= w.
Thì đồ thị nó thỏa nếu như nó không phải là 1 đường thẳng hoặc giữa đường đi đó có những
đỉnh khác chìa ra.

subtask 5: m = n - 1. sub cây.
Mình đang nghĩ đến nhảy nhị phân.
up[0][i]: giá trị nhỏ nhất trong cây con của thằng par[i] mà không đi qua i.
up[j][i]: gia tri nho nhat trong cay con cua thang par[i] ma khong di vao cay con chua nut i.
Xử lý riêng khi đến nút lca.

subtask 6: không còn ràng buộc.
Giả sử mình chặt nhị phân W.
Nếu như ta biết được 1 đường đi từ u đến v thì ta muốn biết là liệu ta có thể đến được
thằng nào nằm ngoài đường đi đó không.

Thì mình sẽ biết là ngoài những đỉnh nằm trên đường đi từ u đến v hay không
thì tôi còn có thể đến được đỉnh nào khác không.

Dựng reachability tree lên thì ta thấy.
**/

const int MAXN = 3e5 + 9;
iii edge[MAXN];
vector<vector<int>> reachTree;
int value[MAXN], weight[MAXN], directPar[MAXN], deg[MAXN];

template<typename T> bool maximize(T &a, T b){ if (a < b) {a = b; return true; } return false;}
template<typename T> bool minimize(T &a, T b){ if (a > b) {a = b; return true; } return false;}

struct DisjointSetUnion{
    vector<int> lab;
    DisjointSetUnion(int _sz = 0){
        lab.resize(_sz + 9, -1);
        fill(lab.begin(), lab.end(), -1);
    }

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

    bool unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            lab[u] += lab[v];
            lab[v] = u;
            return true;
        }
        return false;
    }
};

struct eulerTour{
    vector<int> etour, in, out, depth;
    vector<vector<int>> P;
    int _sz = 0;

    void dfs(vector<vector<int>> &g, int u, int p){
        in[u] = 1;
        P[0][u] = p;
        for(auto v: g[u]){
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(g, v, u);
        }
    }

    void init(){
        in.resize(_sz + 3);
        depth.resize(_sz + 3, 0);
        P.resize(30, vector<int>(_sz + 3, 0));
    }


    int getlca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]){
                u = P[i][u];
            }
        }

        if (u == v) return u;

        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]){
                u = P[i][u];
                v = P[i][v];
            }
        }
        return P[0][v];
    }
    void build(vector<vector<int>> &g){
        _sz = g.size();
        init();

        FORD(i, g.size() - 1, 0){
            if (!in[i]) dfs(g, i, -1);
        }


        FOR(i, 1, 20){
            FOR(j, 0, _sz - 1){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                else P[i][j] = P[i - 1][P[i - 1][j]];
            }
        }
    }

    int Query(int x, int y){
        int acs = getlca(x, y);
        if (value[acs] == 1) return weight[acs];
        FORD(i, 20, 0){
            if (P[i][acs] != -1 and value[P[i][acs]] == 0){
                acs = P[i][acs];
            }
        }
        if (P[0][acs] == -1 or value[P[0][acs]] == 0) return -1;
        else return weight[P[0][acs]];
        return 0;
    }
};

eulerTour etour;
DisjointSetUnion DSU;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    FOR(i, 0, M - 1){
        edge[i] = {W[i], {U[i], V[i]}};
    }

    sort(edge, edge + M);
    reachTree.resize(M);
    DSU = DisjointSetUnion(N + M);
    FOR(i, 0, M - 1){
        int u = edge[i].se.fi;
        int v = edge[i].se.se;
        weight[i] = edge[i].fi;

        int rt1 = DSU.root(u);
        int rt2 = DSU.root(v);
        if (rt1 == rt2) value[i] = 1;
        if (DSU.unite(i + N, rt1)){
            if (rt1 >= N) {
                reachTree[i].pb(rt1 - N);
                deg[i]++;
                deg[rt1 - N]++;

                if (deg[rt1 - N] > 2 or value[rt1 - N]) value[i] = 1;
            }
            else directPar[rt1] = i;
        }

        if (DSU.unite(i + N, rt2)){
            if (rt2 >= N) {
                reachTree[i].pb(rt2 - N);
                deg[i]++;
                deg[rt2 - N]++;
                if (deg[rt1 - N] > 2 or value[rt2 - N]) value[i] = 1;
            }
            else directPar[rt2] = i;
        }
    }
    etour.build(reachTree);
}

int getMinimumFuelCapacity(int X, int Y) {
  int x = directPar[X];
  int y = directPar[Y];
  if (DSU.root(X) != DSU.root(Y)) return -1;
  int res = etour.Query(x, y);
  return res;
  return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 239 ms 31292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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