QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370617#6354. 4Tx_LcyTL 29ms146012kbC++141.9kb2024-03-29 13:50:282024-03-29 13:50:30

Judging History

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

  • [2024-03-29 13:50:30]
  • 评测
  • 测评结果:TL
  • 用时:29ms
  • 内存:146012kb
  • [2024-03-29 13:50:28]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=3e6+10;
int u[N],v[N],d[N],fa[N];ll ans3,ans4,nw;
bool vis[N],gk[N];
vector<int>a[N],s[N];
inline void solve(){
    int n,m;cin>>n>>m;
    rep(i,1,m) cin>>u[i]>>v[i],++d[u[i]],++d[v[i]];
    for (int i=1;i<=m;++i){
    	if (d[u[i]]>d[v[i]]) swap(u[i],v[i]);
    	if (d[u[i]]==d[v[i]] && u[i]>v[i]) swap(u[i],v[i]);
    	a[u[i]].push_back(v[i]);
    }
    int ct=0;
    unordered_map<ll,int>mp;
    for (int i=1;i<=n;++i){
    	for (auto v:a[i]) fa[v]=i;
    	for (auto v:a[i])
    		for (auto w:a[v])
    			if (fa[w]==i){
                    ++ans3;
                    if (!mp[1ll*v*N+w]) mp[1ll*v*N+w]=++ct;
                    s[mp[1ll*v*N+w]].push_back(i);
                }
    }
    rep(i,1,m) a[v[i]].push_back(u[i]);
    vector< pair<int,int> >id;
    rep(i,1,ct){
        int sz=0;
        for (auto j:s[i]) sz+=a[j].size();
        id.push_back({sz,i});
    }
    sort(all(id)),reverse(all(id));
    set<int>ss;
    for (auto k:id){
        int i=k.second;
        for (auto j:s[i]){
            if (!vis[j]){
                ss.insert(j),vis[j]=1;
                for (auto P:a[j]) nw+=vis[P];
            }
            gk[j]=1;
        }
        vector<int>del;
        for (auto i:ss)
            if (!gk[i]) del.push_back(i);
        for (auto i:del){
            ss.erase(i),vis[i]=0;
            for (auto P:a[i]) nw-=vis[P];
        }
        for (auto j:s[i]) gk[j]=0;
        ans4+=nw;
    }
    cout<<ans4<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 29ms
memory: 144452kb

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: 16ms
memory: 144540kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 19ms
memory: 144500kb

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: 24ms
memory: 146012kb

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: 24ms
memory: 145660kb

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: