oj.uz

Submission #673190

# Submission time Handle Problem Language Result Execution time Memory
673190 2022-12-19T22:01:36 Z YENGOYAN Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 21912 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 = 1e9 + 5;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (check(X, Y, m)) r = m;
        else l = m;
    }
    if (r == 1e9 + 5) 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 102 ms 14328 KB Output is correct
10 Correct 146 ms 17484 KB Output is correct
11 Correct 144 ms 17332 KB Output is correct
12 Correct 138 ms 18248 KB Output is correct
13 Correct 139 ms 18264 KB Output is correct
14 Correct 493 ms 15572 KB Output is correct
15 Execution timed out 2086 ms 21912 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 758 ms 20372 KB Output is correct
4 Correct 763 ms 21052 KB Output is correct
5 Correct 798 ms 20760 KB Output is correct
6 Correct 726 ms 21016 KB Output is correct
7 Correct 803 ms 20988 KB Output is correct
8 Correct 784 ms 20272 KB Output is correct
9 Correct 753 ms 20784 KB Output is correct
10 Correct 767 ms 20112 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 102 ms 14328 KB Output is correct
10 Correct 146 ms 17484 KB Output is correct
11 Correct 144 ms 17332 KB Output is correct
12 Correct 138 ms 18248 KB Output is correct
13 Correct 139 ms 18264 KB Output is correct
14 Correct 493 ms 15572 KB Output is correct
15 Execution timed out 2086 ms 21912 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -