QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243451#6354. 4ZeardoeWA 5ms8804kbC++202.9kb2023-11-08 12:06:102023-11-08 12:06:10

Judging History

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

  • [2023-11-08 12:06:10]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:8804kb
  • [2023-11-08 12:06:10]
  • 提交

answer

/*
[templates]: 
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
network_flow
polynomial
lca
bitset
valuesgt
fenwick
erbitree
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
const int N = 100000, sq = sqrt(2 * N); 
vector<int> edge[N + 10], rgt[N + 10]; int deg[N + 10]; int rnk[N + 10]; pii e[N + 10]; 
bool can[N + 10]; int rernk[N + 10]; pii ree[N + 10]; bitset<sq + 5> bs[sq + 5]; 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n, m; cin >> n >> m; 
    f(i, 1, m) {
        int u, v; cin >> u >> v; deg[u] ++; deg[v] ++; e[i] = {u, v}; 
    }
    vector<pii> vec; 
    f(i, 1, n) vec.push_back({deg[i], i});
    sort(vec.begin(), vec.end()); 
    f(i, 0, n - 1) rnk[vec[i].second] = i + 1; 
    f(i, 1, m) {
        int u = rnk[e[i].first], v = rnk[e[i].second]; 
        // cerr << "First Relabel: edge: " << u << " " << v << endl; 
        edge[u].push_back(v); edge[v].push_back(u); 
        if(u > v) swap(u, v); 
        rgt[u].push_back(v); 
    }
    int ans = 0; 
    f(i, 1, n) {
        int cnt = 0; 
        for(int j : rgt[i]) rernk[j] = ++cnt; 
        for(int j : rgt[i]) {
            for(int k : rgt[j]) {
                if(rernk[k]) {
                    ree[++ cnt] = {rernk[j], rernk[k]}; 
                    bs[rernk[j]][rernk[k]] = bs[rernk[k]][rernk[j]] = 1; 
                }
            }
        }
        int tmp = 0; 
        f(j, 1, cnt) {
            int x = ree[j].first, y = ree[j].second; 
            tmp += (bs[x] & bs[y]).count(); 
        }
        ans += tmp / 3; 
        f(j, 1, cnt) bs[j].reset(); 
        for(int j : rgt[i]) rernk[j] = 0; 
    }
    cout << ans << endl; 
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 8324kb

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: 5ms
memory: 8804kb

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: -100
Wrong Answer
time: 4ms
memory: 8664kb

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:

1094346

result:

wrong answer 1st numbers differ - expected: '1094294', found: '1094346'