QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183949#6354. 4ucup-team859WA 0ms3792kbC++172.0kb2023-09-20 02:27:202023-09-20 02:27:21

Judging History

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

  • [2023-09-20 02:27:21]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2023-09-20 02:27:20]
  • 提交

answer

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr int MAXN = (int) 1e5;
constexpr int LIM = 500;

bitset<LIM> adj[LIM + 1];
bitset<LIM> adj3[LIM + 1];

int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edges;
    vector<int> deg(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        deg[x]++, deg[y]++;
        edges.emplace_back(x, y);
    }

    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);
    sort(nodes.begin(), nodes.end(), [&](const int& a, const int& b) {
        return deg[a] < deg[b];
    });

    vector<int> order(n + 1);
    for (int i = 0; i < n; i++) {
        order[nodes[i]] = i;
    }

    vector<vector<int>> g(n + 1);
    for (auto edge : edges) {
        int x = edge.first, y = edge.second;
        if (order[x] > order[y]) {
            swap(x, y);
        }
        g[x].push_back(y);
    }

    vector<int> pos(n + 1);

    ll answer = 0;
    for (auto v : nodes) {
        for (int i = 0; i < (int)g[v].size(); i++) {
            pos[g[v][i]] = i;
        }

        for (auto x : g[v]) {
            adj[pos[x]].reset();
            for (auto y : g[x]) {
                adj[pos[x]][pos[y]] = true;        
            }
            adj3[pos[x]].reset();
        }

        for (auto x : g[v]) {
            for (auto y : g[v]) {
                adj3[pos[x]][pos[y]] = adj[pos[x]][pos[y]];
            }
        }

        for (auto x : g[v]) {
            for (auto y : g[v]) {
                if (!adj[pos[x]][pos[y]]) continue;

                answer += (adj3[pos[x]] & adj3[pos[y]]).count();
            } 
        }
    }

    cout << answer;

    return 0;
}

详细

Test #1:

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

input:

5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3580kb

input:

50 50
28 35
12 24
31 50
10 24
21 44
5 31
23 36
31 45
6 39
4 8
13 37
42 48
17 45
19 33
12 21
19 32
16 43
12 47
25 31
40 48
8 49
43 48
6 42
27 34
13 39
17 40
13 35
3 49
20 24
5 12
43 44
15 37
24 27
8 43
4 22
17 38
28 47
29 46
3 15
9 49
1 41
43 45
3 6
37 48
13 30
11 43
8 25
33 38
16 32
32 41

output:

24

result:

wrong answer 1st numbers differ - expected: '0', found: '24'