Submission #66564409

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, pair<int, int>>;
struct DSU {
    vector<int> parent, rank;
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    void merge(int x, int y) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<ll, pair<int, int>>;

struct DSU {
    vector<int> parent, rank;
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    void merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<pair<int, int>> g;
    priority_queue<P, vector<P>, greater<P>> h;
    DSU dsu(N + Q);

    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        for (int j = 0; j < g.size(); ++j) {
            int s = g[j].first, t = g[j].second;
            h.push({abs(a - s) + abs(b - t), {j + 1, i + 1}});
        }
        g.emplace_back(a, b);
    }

    for (int i = 0; i < Q; ++i) {
        int q;
        cin >> q;
        if (q == 1) {
            int a, b;
            cin >> a >> b;
            N++;
            for (int j = 0; j < g.size(); ++j) {
                int s = g[j].first, t = g[j].second;
                h.push({abs(a - s) + abs(b - t), {j + 1, N}});
            }
            g.emplace_back(a, b);
        } else if (q == 2) {
            ll pre;
            int a, b;
            bool found = false;
            while (!h.empty()) {
                auto top = h.top(); h.pop();
                pre = top.first;
                a = top.second.first;
                b = top.second.second;
                if (!dsu.same(a - 1, b - 1)) {
                    cout << pre << "\n";
                    dsu.merge(a - 1, b - 1);
                    // Merge all same-weighted edges with same weight
                    while (!h.empty() && h.top().first == pre) {
                        auto [_, nodes] = h.top(); h.pop();
                        dsu.merge(nodes.first - 1, nodes.second - 1);
                    }
                    found = true;
                    break;
                }
            }
            if (!found) {
                cout << -1 << "\n";
            }
        } else {
            int a, b;
            cin >> a >> b;
            cout << (dsu.same(a - 1, b - 1) ? "Yes" : "No") << "\n";
        }
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:44:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |         for (int j = 0; j < g.size(); ++j) {
      |                         ~~^~~~~~~~~~
Main.cpp:58:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   58 |             for (int j = 0; j < g.size(); ++j) {
      |                             ~~^~~~~~~~~~

Judge Result