QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100424#6354. 4rniyaTL 165ms4480kbC++172.4kb2023-04-26 01:11:402023-04-26 01:11:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-26 01:11:42]
  • 评测
  • 测评结果:TL
  • 用时:165ms
  • 内存:4480kb
  • [2023-04-26 01:11:40]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

const int MAX_N = 100010;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> es;
    vector<int> deg(n, 0);
    for (; m--;) {
        int u, v;
        cin >> u >> v;
        es.emplace_back(--u, --v);
        deg[u]++;
        deg[v]++;
    }

    vector<vector<int>> G(n);
    for (auto [u, v] : es) {
        if (deg[u] < deg[v] or (deg[u] == deg[v] and u < v))
            G[u].emplace_back(v);
        else
            G[v].emplace_back(u);
    }
    ll ans = 0;
    vector<bitset<MAX_N>> bs(n);
    for (int i = 0; i < n; i++) {
        sort(G[i].begin(), G[i].end());
        for (int& j : G[i]) bs[i][j] = 1;
    }
    for (int u = 0; u < n; u++) {
        vector<pair<int, int>> cand;
        for (int& v : G[u]) {
            bs[v].reset();
            for (int i = 0, j = 0; i < int(G[u].size()) and j < int(G[v].size());) {
                if (G[u][i] == G[v][j]) {
                    int w = G[u][i];
                    bs[v][w] = 1;
                    cand.emplace_back(v, w);
                    i++, j++;
                } else if (G[u][i] < G[v][j])
                    i++;
                else
                    j++;
            }
        }
        for (auto [v, w] : cand) ans += (bs[v] & bs[w]).count();
    }

    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 3480kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3664kb

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: 0
Accepted
time: 165ms
memory: 4480kb

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:

3689634

result:

ok 1 number(s): "3689634"

Test #5:

score: 0
Accepted
time: 88ms
memory: 4432kb

input:

100 4000
73 78
38 98
9 65
43 72
20 47
6 37
49 60
48 87
48 77
23 100
57 59
42 99
40 88
20 96
19 44
35 80
12 93
34 44
63 75
3 49
32 99
47 61
3 13
54 81
55 96
16 74
28 77
43 45
25 92
5 82
3 83
9 55
64 78
39 89
19 64
58 75
1 18
22 76
16 55
18 60
14 55
29 96
37 97
26 97
11 53
24 79
7 35
53 54
31 74
31 32...

output:

1094294

result:

ok 1 number(s): "1094294"

Test #6:

score: -100
Time Limit Exceeded

input:

447 99681
346 391
18 307
271 438
50 436
84 215
64 104
291 325
278 355
152 228
7 117
174 410
61 386
7 204
264 327
366 409
291 405
42 131
89 203
1 175
229 292
225 320
1 310
89 185
161 340
401 406
265 377
119 313
253 403
190 383
305 367
334 424
88 327
77 357
25 334
56 62
68 245
1 13
290 336
94 354
10 3...

output:


result: