oj.uz

답안 #331190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331190 2020-11-27T16:54:52 Z arujbansal 자매 도시 (APIO20_swap) C++17
6 / 100
 379 ms 42092 KB 
#include "swap.h"
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define rand_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

//rand_init;

const int MAXN = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;

struct Edge {
    int u, v, w;

    Edge(int u, int v, int w) : u(u), v(v), w(w) {}

    bool operator<(const Edge &other) {
        return w < other.w;
    }
};

int n, m, fakeNode, timer = 0;
const int MAXK = 20;
vector<Edge> edges;
vi g[MAXN];
int par[MAXN], cost[MAXN], deg[MAXN], binlift[MAXN][MAXK], minCost[MAXN], tin[MAXN], tout[MAXN];
bool valid[MAXN];

void addEdge(int u, int w) {
    g[u].pb(fakeNode);
    g[fakeNode].pb(u);

    cost[fakeNode] = w;
    valid[fakeNode] |= valid[u];
}

int get(int x) {
    return (par[x] == x ? x : par[x] = get(par[x]));
}

void unite(int x, int y, int w) {
//    cout << "Edge unite: " << x << " " << y << " " << w << "\n";

    int u = get(x), v = get(y);

    deg[x]++;
    deg[y]++;

    valid[u] |= (deg[x] >= 3);
    valid[v] |= (deg[y] >= 3);

    u = get(u), v = get(v);

    if (u == v) {
        addEdge(u, w);
        par[u] = fakeNode;
        valid[fakeNode] = true;

        fakeNode++;
        return;
    }

    addEdge(u, w);
    addEdge(v, w);

    par[u] = fakeNode;
    par[v] = fakeNode;

    fakeNode++;
}

void dfs(int u = fakeNode, int p = -1) {
    if (valid[u]) minCost[u] = cost[u];

    if (p != -1) {
        binlift[u][0] = p;
        minCost[u] = min(minCost[u], minCost[p]);
    }

    tin[u] = timer++;

    for (int j = 1; j < MAXK; j++) {
        if (binlift[u][j - 1] < 0) continue;
        binlift[u][j] = binlift[binlift[u][j - 1]][j - 1];
    }

    for (const auto &v : g[u])
        if (v != p)
            dfs(v, u);

    tout[u] = timer - 1;
}

bool isAnc(int x, int y) {
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int queryLCA(int u, int v) {
    if (isAnc(u, v)) return u;
    if (isAnc(v, u)) return v;

    for (int j = MAXK - 1; j >= 0; j--)
        if (binlift[u][j] > -1 && !isAnc(binlift[u][j], v))
            u = binlift[u][j];

    return binlift[u][0];
}

void init(int N, int M, vi U, vi V, vi W) {
    n = N, m = M;
    
    assert(n != 1);

    for (int i = 0; i < m; i++)
        edges.eb(U[i], V[i], W[i]);

    sort(all(edges));

    // Initialise UFDS stuff
    iota(par, par + 2 * n, 0);
    fakeNode = n;

    for (const auto &[u, v, w] : edges)
        unite(u, v, w);

    for (int i = 0; i < MAXN; i++)
        minCost[i] = INF;

    for (int i = 0; i <= 2 * n; i++) {
        for (int j = 0; j < MAXK; j++) {
            binlift[i][j] = -1;
        }
    }

    fakeNode--;
    dfs();
}

int getMinimumFuelCapacity(int X, int Y) {
    int lca = queryLCA(X, Y);

//    cout << "LCA: " << lca << "\n";

    return (minCost[lca] < INF ? minCost[lca] : -1);
}

//void solve() {
//    int a, b;
//    cin >> a >> b;
//    vi u(b), v(b), wt(b);
//
//    for (int i = 0; i < b; i++)
//        cin >> u[i] >> v[i] >> wt[i];
//
//    init(a, b, u, v, wt);
//
//    int q;
//    cin >> q;
//    while (q--) {
//        int x, y;
//        cin >> x >> y;
//        cout << getMinimumFuelCapacity(x, y) << "\n";
//    }
//}
//
//signed main() {
//    FAST_IO;
//#ifdef arujbansal_local
//    setIO("input.txt", "output.txt");
//#endif
//
//    int tc = 1;
////    cin >> tc;
//    while (tc--) solve();
//}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5996 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6124 KB Output is correct
9 Correct 149 ms 28384 KB Output is correct
10 Correct 196 ms 33652 KB Output is correct
11 Correct 179 ms 32992 KB Output is correct
12 Correct 196 ms 34784 KB Output is correct
13 Correct 178 ms 36960 KB Output is correct
14 Correct 163 ms 28512 KB Output is correct
15 Correct 283 ms 35592 KB Output is correct
16 Correct 280 ms 34860 KB Output is correct
17 Correct 286 ms 36552 KB Output is correct
18 Correct 379 ms 38728 KB Output is correct
19 Correct 89 ms 13868 KB Output is correct
20 Correct 274 ms 36688 KB Output is correct
21 Correct 274 ms 35868 KB Output is correct
22 Correct 293 ms 37832 KB Output is correct
23 Correct 345 ms 40136 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 335 ms 40708 KB Output is correct
4 Correct 333 ms 42092 KB Output is correct
5 Incorrect 358 ms 41472 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6124 KB Output is correct
9 Correct 5 ms 6124 KB Output is correct
10 Correct 5 ms 6124 KB Output is correct
11 Correct 7 ms 6124 KB Output is correct
12 Correct 6 ms 6124 KB Output is correct
13 Correct 5 ms 6124 KB Output is correct
14 Correct 6 ms 6252 KB Output is correct
15 Incorrect 5 ms 6124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6124 KB Output is correct
9 Correct 5 ms 6124 KB Output is correct
10 Correct 149 ms 28384 KB Output is correct
11 Correct 196 ms 33652 KB Output is correct
12 Correct 179 ms 32992 KB Output is correct
13 Correct 196 ms 34784 KB Output is correct
14 Correct 178 ms 36960 KB Output is correct
15 Correct 5 ms 6124 KB Output is correct
16 Correct 7 ms 6124 KB Output is correct
17 Correct 6 ms 6124 KB Output is correct
18 Correct 5 ms 6124 KB Output is correct
19 Correct 6 ms 6252 KB Output is correct
20 Incorrect 5 ms 6124 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5996 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6124 KB Output is correct
9 Correct 149 ms 28384 KB Output is correct
10 Correct 196 ms 33652 KB Output is correct
11 Correct 179 ms 32992 KB Output is correct
12 Correct 196 ms 34784 KB Output is correct
13 Correct 178 ms 36960 KB Output is correct
14 Correct 163 ms 28512 KB Output is correct
15 Correct 283 ms 35592 KB Output is correct
16 Correct 280 ms 34860 KB Output is correct
17 Correct 286 ms 36552 KB Output is correct
18 Correct 379 ms 38728 KB Output is correct
19 Correct 335 ms 40708 KB Output is correct
20 Correct 333 ms 42092 KB Output is correct
21 Incorrect 358 ms 41472 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6124 KB Output is correct
9 Correct 5 ms 6124 KB Output is correct
10 Correct 149 ms 28384 KB Output is correct
11 Correct 196 ms 33652 KB Output is correct
12 Correct 179 ms 32992 KB Output is correct
13 Correct 196 ms 34784 KB Output is correct
14 Correct 178 ms 36960 KB Output is correct
15 Correct 163 ms 28512 KB Output is correct
16 Correct 283 ms 35592 KB Output is correct
17 Correct 280 ms 34860 KB Output is correct
18 Correct 286 ms 36552 KB Output is correct
19 Correct 379 ms 38728 KB Output is correct
20 Correct 335 ms 40708 KB Output is correct
21 Correct 333 ms 42092 KB Output is correct
22 Incorrect 358 ms 41472 KB Output isn't correct
23 Halted 0 ms 0 KB -