QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241094#6354. 4jzhWA 1ms10076kbC++201.1kb2023-11-05 23:03:352023-11-05 23:03:36

Judging History

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

  • [2023-11-05 23:03:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10076kb
  • [2023-11-05 23:03:35]
  • 提交

answer


#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int deg[N];

vector<int> G[N];
typedef pair<int, int> pii;
bitset<400> to[N];
int id[N];

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<pii> e;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e.push_back({u, v});
        deg[u]++, deg[v]++;
    }

    for (auto [u, v]: e) {
        if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
        G[u].push_back(v);
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 1;
        memset(id,0,sizeof(id));
        for (int v: G[i]) {
            id[v] = (cnt++);
            to[v].reset();
        }
        for (int v: G[i]) {
            for (int p: G[v]) {
                if (id[p]) {
                    to[v][id[p]] = 1;
                }
            }
        }

        for (int v: G[i]) {
            for (int p: G[v]) {
                ans += (to[v] & to[p]).count();
            }
        }
    }

    cout << ans ;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 8128kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 10076kb

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:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

100 4900
64 78
3 13
93 96
48 64
34 64
5 76
66 74
44 78
17 20
30 73
5 34
24 100
23 65
4 70
22 95
47 70
6 89
15 70
70 82
88 90
29 80
27 64
16 59
28 99
67 68
85 99
37 85
8 46
71 78
40 95
6 21
27 66
16 89
11 83
17 57
19 36
21 70
27 86
27 45
5 56
10 64
23 33
87 91
37 40
21 55
75 79
54 96
3 77
70 78
36 93...

output:

3733007

result:

wrong answer 1st numbers differ - expected: '3689634', found: '3733007'