oj.uz

답안 #673184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673184 2022-12-19T21:55:17 Z YENGOYAN 자매 도시 (APIO20_swap) C++17
0 / 100
 1 ms 340 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>

using namespace std;
using ll = long long;

vector<int> minKox, skizb, verj, par, sizes;
map<pair<int, int>, int> mp;
vector<pair<int, pair<int, int>>> edges;

int get(int u, bool f, int w) {
    if (par[u] == u) return u;
    if (f && mp[{u, par[u]}] <= w) return get(par[u], f, w);
    else if (f) return u;
    return get(par[u], f, w);
}

void union_sets(int u, int v) {
    int a = get(u, 0, 0), b = get(v, 0, 0);
    if (a == b) return;
    if (sizes[a] < sizes[b]) swap(a, b);
    par[b] = a;
    sizes[a] += sizes[b];
}

void mst() {
    sort(edges.begin(), edges.end());
    for (int i = 0; i < edges.size(); ++i) {
        int w = edges[i].first, u = edges[i].second.first, v = edges[i].second.second;
        int p1 = get(u, 0, 0), p2 = get(v, 0, 0);
        if (p1 == p2) continue;
        if (sizes[p1] < sizes[p2]) swap(p1, p2), swap(u, v);
        union_sets(p1, p2);
        if (minKox[p1] || minKox[p2]) {
            skizb[p1] = verj[p1] = -1;
            minKox[p1] = min(minKox[p1], w);
            continue;
        }
        if (skizb[p1] == u && skizb[p2] == v) skizb[p1] = verj[p2];
        else if (skizb[p1] == u && verj[p2] == v) skizb[p1] = skizb[p2];
        else if (verj[p1] == u && verj[p2] == v) verj[p1] = skizb[p2];
        else if (verj[p1] == u && skizb[p2] == v) verj[p1] = verj[p2];
        else {
            verj[p1] = skizb[p1] = -1;
            minKox[p1] = min(minKox[p1], w);
        }
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; ++i) {
        mp[{U[i], V[i]}] = mp[{V[i], U[i]}] = W[i];
        edges.push_back({ W[i], {U[i], V[i]} });
    }
    mst();
}

bool check(int x, int y, int w) {
    int p1 = get(x, 1, w), p2 = get(y, 1, w);
    if (p1 != p2) return 0;
    if (minKox[p1] > w) return 0;
    return 1;
}

int getMinimumFuelCapacity(int X, int Y) {
    ll l = 0, r = 1e15;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (check(X, Y, m)) r = m;
        else l = m;
    }
    cout << r << endl;
    return 0;
}

Compilation message

swap.cpp: In function 'void mst()':
swap.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < edges.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -