QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102086#6354. 4whateverWA 3ms7936kbC++141.4kb2023-05-02 12:00:162023-05-02 12:00:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-02 12:00:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7936kb
  • [2023-05-02 12:00:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rep(i, a, b) for (int i = (a), I = (b); i <= I; ++i)
#define per(i, a, b) for (int i = (a), I = (b); i >= I; --i)
using i64 = long long;
using pii = pair<int, int>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

const int N = 100005, B = 500;
int n, m, d[N], x[N], y[N], ord[N], rk[N], id[N], pot[B];
vector<int> e[N];
bitset<B> g[B];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;
    rep(i, 1, m) cin >> x[i] >> y[i], ++d[x[i]], ++d[y[i]];

    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&](int i, int j) {
        return pii(d[i], i) < pii(d[j], j);
    });
    rep(i, 1, n) rk[ord[i]] = i;
    rep(i, 1, m) {
        if (rk[x[i]] > rk[y[i]]) swap(x[i], y[i]);
        e[x[i]].push_back(y[i]);
    }

    i64 ans = 0;
    rep(o, 1, n) {
        int u = ord[o];
        int cnt = 0;
        for (auto v : e[u]) id[v] = ++cnt, pot[cnt] = v;
        rep(i, 1, cnt) {
            g[i].reset();
            int u = pot[i];
            for (auto v : e[u]) if (id[v]) g[i].set(id[v]);
        }
        rep(i, 1, cnt) rep(j, i + 1, cnt) ans += (g[i] & g[j]).count();
        for (auto v : e[u]) id[v] = 0;
    }
    cout << ans << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 7880kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

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: 3ms
memory: 6320kb

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:

3725593

result:

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