oj.uz

답안 #848980

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848980 2023-09-13T19:19:45 Z tvladm2009 자매 도시 (APIO20_swap) C++17
0 / 100
 0 ms 348 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int)1e9 + 7;
vector<int> t;
vector<int> dim;
vector<bool> is_line;
vector<int> when;
vector<bool> endpoint;
vector<int> when_join;
int n, m;

void clr() {
        t.resize(n + 1);
        dim.resize(n + 1);
        is_line.resize(n + 1);
        when.resize(n + 1);
        endpoint.resize(n + 1);
        when_join.resize(n + 1);
        for (int i = 1; i <= n; i++) {
                t[i] = i;
                dim[i] = 1;
                is_line[i] = 1;
                when_join[i] = 1;
                when[i] = -1;
        }
}

int root(int a) {
        if (a == t[a]) {
                return a;
        }
        else {
                return t[a];
        }
}

void join(int a, int b, int val) {
        int x = root(a);
        int y = root(b);
        if (a == b) {
                if (is_line[a] == 1) {
                        when[a] = val;
                }
                is_line[a] = 0;
                return;
        }
        if (dim[a] < dim[b]) {
                swap(a, b);
                swap(x, y);
        }
        if (is_line[a] && is_line[b] && endpoint[x] && endpoint[y]) {
                is_line[a] = 1;
                if (dim[a] > 1) {
                        endpoint[x] = 0;
                }
                if (dim[b] > 1) {
                        endpoint[y] = 0;
                }
        }
        else {
                if (is_line[a] == 1) {
                        when[a] = val;
                        is_line[a] = 0;
                }
        }
        when_join[b] = val;
        dim[a] += dim[b];
        t[b] = a;
}

struct Edge {
        int a;
        int b;
        int w;
};

bool operator < (Edge a, Edge b) {
        return a.w < b.w;
}

vector<Edge> edges;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
        assert((int)U.size() == M);
        assert((int)V.size() == M);
        assert((int)W.size() == M);

        n = N;
        m = M;
        edges.clear();
        for (int i = 0; i < m; i++) {
                edges.push_back({U[i], V[i], W[i]});
        }
        sort(edges.begin(), edges.end());
        clr();
        for (auto& edg : edges) {
                join(edg.a, edg.b, edg.w);
        }
}

int getMinimumFuelCapacity(int x, int y) {
        if (x == y) {
                return 0;
        }
        vector<int> path_x, path_y;
        while (1) {
                path_x.push_back(x);
                if (x == t[x]) {
                        break;
                }
                x = t[x];
        }
        while (1) {
                path_y.push_back(y);
                if (y == t[y]) {
                        break;
                }
                y = t[y];
        }
        reverse(path_x.begin(), path_x.end());
        reverse(path_y.begin(), path_y.end());
        bool deja = 0;
        int wjoin = 0;
        for (int i = max((int)path_x.size(), (int)path_y.size()) - 1; i >= 0; i--) {
                if (i < (int)path_x.size() && i < (int)path_y.size() && path_x[i] == path_y[i]) {
                        if (deja) {
                                return wjoin;
                        }
                        if (when[path_x[i]] != -1) {
                                return max(wjoin, when[path_x[i]]);
                        }
                }
                if (i < (int)path_x.size()) {
                        if (when[path_x[i]] != -1) {
                                deja = 1;
                        }
                        wjoin = max(wjoin, when_join[path_x[i]]);
                }
                if (i < (int)path_y.size()) {
                        if (when[path_y[i]] != -1) {
                                deja = 1;
                        }
                        wjoin = max(wjoin, when_join[path_y[i]]);
                }
        }
        return -1;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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