oj.uz

답안 #673187

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673187 2022-12-19T21:59:26 Z YENGOYAN 자매 도시 (APIO20_swap) C++17
7 / 100
 2000 ms 26680 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] != 2e9 || minKox[p2] != 2e9) {
            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) {
    minKox = vector<int>(N, 2e9);
    skizb = verj = par = sizes = vector<int>(N);
    for (int i = 0; i < N; ++i) {
        skizb[i] = verj[i] = par[i] = i;
        sizes[i] = 1;
    }
    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;
    }
    if (r == 1e15) return -1;
    else return r;
    //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 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 101 ms 16080 KB Output is correct
10 Correct 133 ms 19624 KB Output is correct
11 Correct 128 ms 19304 KB Output is correct
12 Correct 139 ms 20304 KB Output is correct
13 Correct 155 ms 20392 KB Output is correct
14 Correct 341 ms 17188 KB Output is correct
15 Execution timed out 2049 ms 26680 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 997 ms 24220 KB Output is correct
4 Correct 973 ms 25040 KB Output is correct
5 Correct 1034 ms 24708 KB Output is correct
6 Correct 961 ms 24812 KB Output is correct
7 Correct 1022 ms 24928 KB Output is correct
8 Correct 997 ms 24152 KB Output is correct
9 Correct 995 ms 24592 KB Output is correct
10 Correct 1016 ms 23960 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 101 ms 16080 KB Output is correct
10 Correct 133 ms 19624 KB Output is correct
11 Correct 128 ms 19304 KB Output is correct
12 Correct 139 ms 20304 KB Output is correct
13 Correct 155 ms 20392 KB Output is correct
14 Correct 341 ms 17188 KB Output is correct
15 Execution timed out 2049 ms 26680 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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