QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#154111#6354. 4PhantomThresholdTL 157ms10736kbC++202.3kb2023-08-31 13:43:352023-08-31 13:43:36

Judging History

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

  • [2023-08-31 13:43:36]
  • 评测
  • 测评结果:TL
  • 用时:157ms
  • 内存:10736kb
  • [2023-08-31 13:43:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

namespace K4{
	typedef long long ll;
	const int maxn=100000;
	int n,m;
	vector<int> g[maxn+50];
	int deg[maxn+50];
	void init(){
		
		cin >> n >> m;
		for (int i=1;i<=m;i++){
			int x,y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
			deg[x]++;
			deg[y]++;
		}
		
		/*
		n=100;
		m=n*(n-1)/2;
		for (int x=1;x<=n;x++){
			for (int y=x+1;y<=n;y++){
				g[x].push_back(y);
				g[y].push_back(x);
				deg[x]++;
				deg[y]++;
			}
		}
		*/
	}
	bitset<maxn+1> ok[1000];
	ll gao(ll n,const vector<vector<int>> &G){
		ll ans=0;
		for (int u=1;u<=n;u++){
			for (auto v:G[u]){
				ans+=(ok[u]&ok[v]).count();
			}
		}
		return ans;
	}
	vector<int> G[maxn+50];
	ll solve(){
		ll ans=0;
		vector<int> order(n+5);
		for (int i=1;i<=n;i++) order[i]=i;
		sort(order.begin()+1,order.begin()+n+1,
			[&](int x,int y){
				return (deg[x]==deg[y])?(x<y):(deg[x]<deg[y]);	
			}
		);
		vector<int> rk(n+5);
		for (int i=1;i<=n;i++) rk[order[i]]=i;
		for (int u=1;u<=n;u++){
			for (auto v:g[u]) if (rk[u]<rk[v]){
				G[rk[u]].push_back(rk[v]);	
			}
		}
		for (int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
		
	//	cerr << clock() << endl;
		
		vector<vector<int>> subG(n+1);
		vector<int> id(n+1);
		for (int u=1;u<=n;u++){
			int top=0;
			for (auto v:G[u]) id[v]=++top;
			/*
			cerr << "----------------" << endl;
			cerr << "work " << u << endl;
			cerr << "top : " << top << endl;
			for (int i=1;i<=n;i++) cerr << id[i] << " ";
			cerr << endl;
			*/
			vector<vector<int>> tag(n+1);
			for (auto v:G[u]){
				for (auto w:G[v]) tag[w].push_back(v);
				for (auto w:tag[v]){
					subG[id[w]].push_back(id[v]);
					ok[id[w]][id[v]]=1;
				}	
			}
			/*
			for (int i=1;i<=top;i++){
				cerr << i << " : ";
				for (auto v:subG[i]) cerr << v << " ";
				cerr << " ";
				for (int j=0;j<=top;j++) cerr << ok[i][j];
				cerr << endl;
			}
			*/
			ans=ans+gao(top,subG);
			for (int i=1;i<=top;i++){
				ok[i]=0;
				subG[i].clear();
			}
		//	cerr << "ans : " << ans << endl;
		}
	//	cerr << clock() << endl;
		return ans;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
//	freopen("err.txt","w",stderr);
	K4::init();
	cout << K4::solve() << "\n";
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10560kb

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

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 10448kb

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: 157ms
memory: 10736kb

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: 87ms
memory: 10632kb

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: