QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669861#8760. 不等式zwu2021016689WA 2ms12336kbC++171.5kb2024-10-23 19:52:122024-10-23 19:52:12

Judging History

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

  • [2024-10-23 19:52:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12336kb
  • [2024-10-23 19:52:12]
  • 提交

answer

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

#define int long long
#define dg(x) cout<<#x<<'='<<x<<'\n';
#define all(x) x.begin(),x.end()

const int N=2e5+10;

vector<int>g[N];
int vis[N],dis[N],in[N];
int co=0;
int ans=0;
int root;
set<int>s;

void dfs(int x){
	//dg(x)
	if(co==1) return ;
	if(s.find(x)!=s.end()){
		co=1;
		return ;
	}
	s.insert(x);
	if(vis[x]){
		s.erase(s.find(x));
		return ;
	}
	vis[x]=1;
	for(auto u:g[x]){
		dfs(u);
	}
	if(g[x].size()==0){
		dis[x]=1;
	}
	else{
		vector<int>v;
		for(auto u:g[x]) v.push_back(dis[u]);
		sort(all(v),greater<int>());
		dis[x]+=v[0];
		if(v.size()>=2) dis[x]+=v[1];
	}
	s.erase(s.find(x));
}

inline void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back(y);
		g[x].push_back(z);
		in[y]++;
		in[z]++;
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(in[i]==0) q.push(i);
	}
	set<int>st;
	while(q.size()){
		int u=q.front();
		st.insert(u);
		q.pop();
		for(auto v:g[u]){
			in[v]--;
			if(in[v]==0) q.push(v);
		}
	}
	if(st.size()!=n){
		cout<<-1;
		return ;
	}
	
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i);
		s.clear();
	}
	
	for(int i=1;i<=n;i++) ans+=dis[i];
	//if(co) ans=-1;
	cout<<ans<<'\n';
}
/*
5 2
1 2 3
3 1 2

6 3
1 2 3
3 4 5
6 3 5

3 1
1 2 2

10 3
1 2 3
1 8 8
2 3 3
*/

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12024kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

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

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

input:

5 2
1 2 3
2 3 4

output:

8

result:

ok 1 number(s): "8"

Test #11:

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

input:

10 1
1 2 3

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

10 1
1 2 2

output:

11

result:

ok 1 number(s): "11"

Test #13:

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

input:

10 2
1 2 3
2 3 4

output:

13

result:

ok 1 number(s): "13"

Test #14:

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

input:

10 2
1 2 2
2 3 4

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

input:

10 3
1 2 3
1 8 8
2 3 3

output:

13

result:

ok 1 number(s): "13"

Test #16:

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

input:

20 1
1 2 2

output:

21

result:

ok 1 number(s): "21"

Test #17:

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

input:

20 2
1 2 3
2 3 3

output:

23

result:

ok 1 number(s): "23"

Test #18:

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

input:

20 3
7 14 6
1 2 3
4 7 20

output:

24

result:

ok 1 number(s): "24"

Test #19:

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

input:

20 4
1 2 2
6 10 6
2 3 3
3 4 5

output:

-1

result:

ok 1 number(s): "-1"

Test #20:

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

input:

20 5
1 17 3
1 2 3
2 3 4
3 4 5
8 13 16

output:

28

result:

ok 1 number(s): "28"

Test #21:

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

input:

200 9
1 2 2
2 3 3
3 4 5
91 112 195
126 145 82
4 5 5
53 2 15
5 6 6
6 7 7

output:

318

result:

ok 1 number(s): "318"

Test #22:

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

input:

200 17
1 2 2
100 69 47
159 84 111
2 3 3
3 4 5
4 5 5
8 9 76
5 6 7
158 81 154
189 62 45
192 159 181
6 7 7
15 181 91
7 193 152
140 65 66
7 8 9
32 157 67

output:

428

result:

ok 1 number(s): "428"

Test #23:

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

input:

200 25
118 152 40
172 193 173
126 32 89
1 2 3
147 148 112
2 3 4
3 4 4
35 116 95
179 193 64
70 22 55
4 5 5
5 6 6
24 74 182
184 168 129
6 7 8
7 8 9
109 63 173
8 9 10
38 125 106
68 147 40
33 65 46
144 12 168
9 10 11
10 11 11
190 73 48

output:

835

result:

ok 1 number(s): "835"

Test #24:

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

input:

200 33
1 2 3
165 80 199
2 3 4
10 80 12
3 4 5
4 5 6
5 6 7
128 1 190
6 7 7
166 124 95
7 8 9
60 51 80
25 158 81
108 107 99
8 9 9
9 10 10
10 11 12
54 41 100
11 12 13
176 185 149
12 13 13
13 14 14
14 15 16
15 16 17
16 17 17
128 73 196
17 18 19
93 169 141
18 19 19
19 20 20
20 21 21
21 22 22
12 55 32

output:

543121

result:

ok 1 number(s): "543121"

Test #25:

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

input:

200 41
1 2 3
2 3 3
3 4 4
4 5 5
175 3 161
5 6 7
6 7 8
7 8 9
8 9 10
9 10 10
10 11 11
24 15 157
82 57 72
161 48 197
149 96 16
30 3 131
165 114 21
143 110 56
11 12 12
12 13 13
13 14 14
62 183 153
14 15 15
15 16 16
192 139 91
178 54 86
16 17 18
158 59 18
17 18 19
35 91 197
18 19 20
99 129 43
168 76 146
7...

output:

-1

result:

ok 1 number(s): "-1"

Test #26:

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

input:

2000 81
97 630 1373
398 361 536
1 2 3
2 3 4
3 4 5
1573 1392 1526
645 1562 79
1833 239 840
4 5 5
1122 972 412
5 6 7
1089 190 1311
672 1664 887
6 7 8
805 1221 1635
7 8 8
8 9 9
1001 1271 267
176 200 567
1800 762 1129
1978 1273 429
1965 155 68
295 1714 836
499 1093 465
9 10 11
10 11 11
11 12 13
12 13 14...

output:

1474361

result:

ok 1 number(s): "1474361"

Test #27:

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

input:

2000 161
594 271 957
633 1085 1384
1133 1233 916
1463 1353 621
1 2 2
514 1052 224
814 744 1837
44 195 1186
2 3 4
1272 606 1531
739 706 1827
1862 1014 834
3 4 5
4 5 5
1063 1246 1103
935 318 593
1657 93 324
583 987 1283
1258 1051 866
1187 1012 1167
1427 1825 589
5 6 7
1055 141 69
491 1545 487
739 1255...

output:

47813842

result:

ok 1 number(s): "47813842"

Test #28:

score: -100
Wrong Answer
time: 0ms
memory: 9440kb

input:

2000 241
410 1433 1627
1489 1395 611
1 2 3
2 3 3
1553 1507 1544
3 4 4
4 5 5
1073 1318 1088
112 333 87
1322 187 439
461 1272 1516
1385 813 1044
784 954 1186
449 53 531
5 6 6
644 1277 1454
76 1249 1631
1233 992 209
310 416 447
909 227 1268
956 594 1727
1576 1567 116
1954 1245 1988
1755 1154 437
1539 1...

output:

3241883560

result:

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