oj.uz

답안 #964060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964060 2024-04-16T09:08:46 Z efedmrlr 자매 도시 (APIO20_swap) C++17
0 / 100
 390 ms 93092 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 19;
constexpr int MOD = 1e9+7;
int n,m,q;

struct DSU {
    vector<int> p, sz;
    void reset(int s) {
        p.assign(s + 3, 0);
        sz.assign(s + 3, 1);
    }
    void make_set(int x) {
        p[x] = x;
    }
    int find_set(int x) {
        return (p[x] == x) ? x : p[x] = find_set(p[x]);
    }
    bool union_set(int x, int y) {
        x = find_set(x); y = find_set(y);
        if(x == y) return 0;
        if(sz[y] > sz[x]) swap(x, y);
        sz[x] += sz[y];
        p[y] = x;
        return 1;
    }

};



vector<vector<int> > adj;
vector<vector<int> > anc;
vector<vector<int> > pcost, cst;
vector<int> dep;
vector<array<array<int, 2>, 3> > cost3; 
vector<array<int,3> > edges;
DSU ds;

void prec(int node, int par, vector<vector<array<int,2> > > &tmp) {
    vector<array<int,2> >::iterator mnc;
    anc[node][0] = par;
    int mn = INF;
    for(auto itr = tmp[node].begin(); itr != tmp[node].end(); ) {
        auto &c = *itr;
        if(c[0] == par) {  
            pcost[node][0] = pcost[n + node][0] = c[1];

            itr = tmp[node].erase(itr);
            continue;
        }   
        if(mn > c[1]) {
            mn = c[1];
            mnc = itr;
        }
        dep[c[0]] = dep[c[0] + n] = dep[node] + 1;
        prec(c[0], node, tmp);
        itr++;
    }
    if(tmp[node].empty()) return;
    adj[n + node].pb((*mnc)[0]);
    anc[(*mnc)[0]][0] = n + node;
    cst[node][0] = mn;
    cst[n + node][0] = INF;
    for(auto itr = tmp[node].begin(); itr != tmp[node].end(); itr++) {
        if(itr == mnc) continue;
        cst[n + node][0] = min(cst[n + node][0], (*itr)[1]);
        adj[node].pb((*itr)[0]);
    }


}

void calc() {
    for(int k = 1; k < LGN; k++) {
        for(int i = 0; i <= 2*n; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
            pcost[i][k] = max(pcost[i][k - 1], pcost[anc[i][k - 1]][k - 1]);
            cst[i][k] = min(cst[i][k - 1], cst[anc[i][k - 1]][k - 1]);
        }
    }
}

int kth_anc(int a, int k) {
    for(int i = 0; i < LGN; i++) {
        if(k & (1 << i)) {
            a = anc[a][i];
        }
    }
    return a;
}
int lca(int a, int b) {
    if(dep[a] > dep[b]) swap(a, b);
    b = kth_anc(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int k = LGN - 1; k>=0; k--) {
        if(anc[a][k] != anc[b][k]) {
            a = anc[a][k];
            b = anc[b][k];
        }
    }
    return anc[a][0];
}
int get_dist(int a, int b) {
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int get_cst(int a, int b) {
    // b is anc of a
    // [a, b)
    int ans = INF;
    for(int k = LGN - 1; k>=0; k--) {
        if(dep[anc[a][k]] > dep[b]) {
            ans = min(ans, cst[a][k]);
            a = anc[a][k];
        }
    }
    return ans;
}
int get_pcost(int a, int b) {
    // b is anc of a
    // [a, b)
    int ans = 0;
    for(int k = LGN - 1; k>=0; k--) {
        if(dep[anc[a][k]] > dep[b]) {
            ans = max(ans, pcost[a][k]);
            a = anc[a][k];
        }
    }
    return ans;
}
int get_lca_cost(int a, int b, int lc) {
    if(a != lc) a = kth_anc(a, dep[a] - dep[lc] - 1);
    if(b != lc) b = kth_anc(b, dep[b] - dep[lc] - 1);
    for(auto &c : cost3[lc]) {
        if(c[0] != a && c[0] != b) return c[1];
    }
    return INF;
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    edges.resize(M);
    adj.assign(2 * N + 5, vector<int>());
    for(int i = 0; i < M; i++) {
        edges[i] = {W[i], U[i], V[i]};
    }
    sort(all(edges));
    ds.reset(N);
    for(int i = 0; i < N; i++) ds.make_set(i);
    vector<vector<array<int,2> > > tmp(N, vector<array<int,2> >());
    
    pcost.assign(2*N + 5, vector<int>(LGN, 0));
    cst.assign(2*N + 5, vector<int>(LGN, INF));
    anc.assign(2*N + 5, vector<int>(LGN, 2 * N));
    anc[2*N][0] = 2 * N;
    dep.assign(2*N + 5, 0);
    for(auto &c : edges) {
        if(ds.union_set(c[1], c[2])) {
            tmp[c[1]].pb({c[2], c[0]});
            tmp[c[2]].pb({c[1], c[0]});
        }
    }
    cost3.resize(2*N + 5);
    for(int i = 0; i < 2*N + 5; i++) {
        REP(j, 3) cost3[i][j] = {0, INF};
    }
    for(int i = 0; i < N; i++) {
        sort(all(tmp[i]), [](array<int,2> &x, array<int,2> &y) {
            return x[1] < y[1];
        });
        for(int j = 0; j < min(3, (int)tmp[i].size()); j++) {
            cost3[i][j] = cost3[i + N][j] = tmp[i][j];
        }
    }


    prec(0, 2*N, tmp);
    calc();

}

int getMinimumFuelCapacity(int X, int Y) {
    int u, v, mn = INF;
    REP(i, 2) {
        REP(j, 2) {
            int tmp = get_dist(X + i * n, Y + j * n);
            if(tmp < mn) {
                mn = tmp;
                u = X + i * n;
                v = Y + j * n;
            }
        }
    }
    int lc = lca(u, v);
    // cout << "u:" << u << " v:" << v << " lc:" << lc << "\n";
    int ans = max(get_pcost(v, lc), get_pcost(u, lc));
    int cost = INF;
    if(lc != u) cost  = min(cost, get_cst(anc[u][0], lc));
    if(lc != v) cost = min(cost, get_cst(anc[v][0], lc));
    cost = min(cost, get_lca_cost(u, v, lc));
    ans = max(ans, cost);
    if(ans == INF) return -1;
    return ans;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:222:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |     cost = min(cost, get_lca_cost(u, v, lc));
      |                      ~~~~~~~~~~~~^~~~~~~~~~
swap.cpp:222:34: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 390 ms 93092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -