oj.uz

답안 #849006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849006 2023-09-13T20:58:50 Z tvladm2009 자매 도시 (APIO20_swap) C++17
0 / 100
 0 ms 344 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<int> is_line;
vector<int> when;
vector<int> endpoint;
vector<int> when_join;
int n, m;

void clr() {
        t.resize(n);
        dim.resize(n);
        is_line.resize(n);
        when.resize(n);
        endpoint.resize(n);
        when_join.resize(n);
        for (int i = 0; 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 root(t[a]);
        }
}

void join(int a, int b, int val) {
        int x = a, y = b;
        a = root(a);
        b = 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() - 1, (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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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