Submission #19555250

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <chrono>

using namespace std;

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    UnionFind(int N) : par(N), rank(N) {
        for(int i = 0; i < N; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }
    
    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        return true;
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

int main(int argc, const char * argv[]) {

    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M; cin >> N >> M;
    vector<int> a(M), b(M);
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    int Q; cin >> Q;
    vector<int> x(Q), y(Q);
    for (int i = 0; i < Q; i++) {
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
    }
    
    if (M == 0) {
        for (int i = 0; i < Q; i++) cout << -1 << endl;
        return 0;
    }
    
    vector<int> yes(Q, M + 1), no(Q, 0);
    
    while (true) {
        bool update = false;
        for (int i = 0; i < Q; i++) {
            if (yes[i] - no[i] != 1) {
                update = true;
                break;
            }
        }
        if (!update) break;
        
        vector<vector<int>> mid(M + 1);
        for (int i = 0; i < Q; i++) mid[(yes[i] + no[i]) / 2].emplace_back(i);
        
        UnionFind tree(N);
        
        for (int i = 1; i <= M; i++) {
            tree.unite(a[i - 1], b[i - 1]);
            for (int j : mid[i]) {
                if (tree.same(x[j], y[j])) yes[j] = i; else no[j] = i;
            }
        }
    }
    
    for (int i = 0; i < Q; i++) {
        cout << (yes[i] == M + 1 ? -1 : yes[i]) << endl;
    }
    
    return 0;
    
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:45:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
   45 | int main(int argc, const char * argv[]) {
      |          ~~~~^~~~
./Main.cpp:45:33: warning: unused parameter ‘argv’ [-Wunused-parameter]
   45 | int main(int argc, const char * argv[]) {
      |                    ~~~~~~~~~~~~~^~~~~~

Judge Result