QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90143#5672. Connectivity ProblemChatGPTWA 35ms3324kbC++1.1kb2023-03-22 13:43:562023-03-22 13:44:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 13:44:00]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:3324kb
  • [2023-03-22 13:43:56]
  • 提交

answer

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000;

int p[MAXN+1]; // parent array for union-find

// initialize the parent array for union-find
void make_set(int n) {
    for (int i = 0; i <= n; i++) {
        p[i] = i;
    }
}

// find the parent of a set in union-find
int find_set(int x) {
    if (p[x] != x) {
        p[x] = find_set(p[x]);
    }
    return p[x];
}

// union two sets in union-find
void union_sets(int x, int y) {
    int px = find_set(x), py = find_set(y);
    if (px != py) {
        p[px] = py;
    }
}

int main() {
    int n;
    cin >> n;

    make_set(MAXN); // initialize the parent array

    while (n--) {
        int p, q;
        cin >> p >> q;

        if (find_set(p) != find_set(q)) {
            union_sets(p, q);
        }
    }

    int k;
    cin >> k;

    while (k--) {
        int p, q;
        cin >> p >> q;

        if (find_set(p) == find_set(q)) {
            cout << "Y" << endl;
        } else {
            cout << "N" << endl;
        }
    }

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 35ms
memory: 3324kb

input:

12
3 4
4 9
8 1
2 3
5 6
2 9
5 9
7 3
4 8
5 6
1 8
6 1

output:

Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
...

result:

wrong answer 1st lines differ - expected: 'N', found: 'Y'