QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202634#5531. ICCCamillus0 1ms4084kbC++201.1kb2023-10-06 12:43:192023-10-06 12:43:20

Judging History

你现在查看的是测评时间为 2023-10-06 12:43:20 的历史记录

  • [2024-07-01 04:28:19]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:0ms
  • 内存:4128kb
  • [2023-10-06 12:43:20]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4084kb
  • [2023-10-06 12:43:19]
  • 提交

answer

#include "bits/stdc++.h"
#include "icc.h"
using namespace std;

struct dsu {
    vector<int> p;
    vector<vector<int>> d;

    dsu(int n) {
        p.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            d[i] = {i};
        }
    }

    int get(int u) {
        if (u == p[u]) {
            return u;
        } else {
            return p[u] = get(p[u]);
        }
    }

    void join(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        if (d[v].size() > d[u].size()) {
            swap(u, v);
        }
        p[v] = u;
        d[u].insert(d[u].end(), d[v].begin(), d[v].end());
        d[v].clear();
    }
};

void run(int n) {
    dsu Q(n);
    int cnt = 0;
    for (int u = 0; u < n && cnt != n - 1; u++) {
        for (int v = 0; v < n && cnt != n - 1; v++) {
            if (Q.get(u) != Q.get(v)) {
                if (query(1, 1, &u, &v)) {
                    setRoad(u, v);
                    cnt++;
                }
            }
        }
    }
}

详细

Subtask #1:

score: 0
Acceptable Answer

Test #1:

score: 0
Acceptable Answer
time: 0ms
memory: 4084kb

input:

1
1500 3
15

0
2

0.0
2.5

0
3.5

0

1 1

output:

0
Query cities not in range [1, n]

result:

points inf0

Subtask #2:

score: 0
Acceptable Answer

Test #3:

score: 0
Acceptable Answer
time: 1ms
memory: 4008kb

input:

1
2500 4
50

0
0

0.0
3.5

0
2.5

5

1 1

output:

0
Query cities not in range [1, n]

result:

points inf0

Subtask #3:

score: 0
Acceptable Answer

Test #6:

score: 0
Acceptable Answer
time: 1ms
memory: 3956kb

input:

1
2250 6
100

0.05
2.3

0.1
0.7

0
1.5

1.7

1.1 1

output:

0
Query cities not in range [1, n]

result:

points inf0

Subtask #4:

score: 0
Acceptable Answer

Test #10:

score: 0
Acceptable Answer
time: 0ms
memory: 4040kb

input:

1
2000 5
100

0.01
1.00

0.10
1.70

0.00
1.50

5.0

1.20 1

output:

0
Query cities not in range [1, n]

result:

points inf0

Subtask #5:

score: 0
Acceptable Answer

Test #14:

score: 0
Acceptable Answer
time: 0ms
memory: 4024kb

input:

1
1775 4
100

0.00
0.00

0.00
2.70

0.10
7.55

0.0

1.15 1

output:

0
Query cities not in range [1, n]

result:

points inf0

Subtask #6:

score: 0
Acceptable Answer

Test #20:

score: 0
Acceptable Answer
time: 0ms
memory: 4040kb

input:

1
1625 5
100

0.00
0.00

0.00
3.00

0.00
1.00

0.0

3 1

output:

0
Query cities not in range [1, n]

result:

points inf0