QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323321#6765. Don't Really Like How The Story EndsRico64WA 213ms3628kbC++201.1kb2024-02-09 09:33:092024-02-09 09:33:10

Judging History

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

  • [2024-02-09 09:33:10]
  • 评测
  • 测评结果:WA
  • 用时:213ms
  • 内存:3628kb
  • [2024-02-09 09:33:09]
  • 提交

answer

#include <iostream>
#include <set>
#include <stack>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    set<int> graph[n];
    for (int i = 0, f, t; i < m; ++i) {
        cin >> f >> t;
        f--; t--;
        if (t < f) swap(f, t);
        if (f == t) continue;
        graph[f].insert(t);
        graph[t].insert(f);
    }
    int res = 0;
    int parent[n];
    fill(parent, parent + n, -1);
    for (int s = 0; s < n - 1; ++s) {
        int i = s;
        while (i >= 0) {
            while (!graph[i].empty() && *graph[i].begin() <= s) {
                graph[i].erase(graph[i].begin());
            }
            if (!graph[i].empty()) break;
            i = parent[i];
        }
        if (i < 0) i = 0;
        if (!graph[i].empty() && *graph[i].begin() == s + 1) {
            continue;
        }
        graph[i].insert(s + 1);
        graph[s + 1].insert(i);
        res++;
        parent[s + 1] = i;
    }

    cout << res << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

3
2 3
1 1
1 2
2 1
4 1
1 4
4 2
1 2
3 4

output:

0
2
1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 213ms
memory: 3560kb

input:

117747
3 7
2 1
3 3
1 3
1 1
3 2
1 1
3 1
4 8
2 3
4 3
3 2
4 2
1 3
2 1
4 3
2 4
3 4
2 3
2 2
3 3
1 1
2 5
1 1
2 2
2 2
1 2
2 2
3 7
2 1
1 2
3 3
3 2
1 2
3 3
3 2
4 5
1 2
3 3
4 4
1 4
2 1
3 1
3 2
1 3
1 1
1 1
1 1
1 6
1 1
1 1
1 1
1 1
1 1
1 1
5 4
2 1
2 5
1 3
3 2
4 7
1 1
2 4
3 2
1 1
1 1
4 2
2 3
5 8
3 3
2 2
4 2
1 4
1...

output:

0
0
1
0
0
1
1
0
0
2
2
2
0
0
2
0
2
0
1
0
1
3
0
0
0
2
1
1
1
0
0
0
2
0
3
1
3
0
2
1
3
1
2
1
0
0
1
2
0
2
0
1
2
0
0
2
0
0
1
1
0
3
0
2
0
0
1
1
0
3
2
0
0
0
1
0
2
3
0
1
1
1
1
1
0
2
1
3
0
1
2
0
0
0
3
0
0
3
1
0
2
0
0
0
1
0
1
0
0
0
0
4
0
0
0
0
1
0
3
0
2
1
0
1
1
0
0
2
0
1
0
1
0
2
1
1
2
1
0
1
0
1
0
1
1
2
1
0
0
1
...

result:

wrong answer 10th lines differ - expected: '1', found: '2'