QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604674#8760. 不等式xing4c#WA 4ms14108kbC++141.5kb2024-10-02 13:01:262024-10-02 13:01:26

Judging History

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

  • [2024-10-02 13:01:26]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:14108kb
  • [2024-10-02 13:01:26]
  • 提交

answer

#include <bits/stdc++.h>
#define NOSYNC ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define int ll
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 200005;

// -------------- Templates Above -------------------------

int a[N]; int n, m;
vector<int> G[N];
int in[N]; int vis[N]; int d[N];

void dfs1(int x) {
	// cout << "dfs1: " << x << endl;
	if(vis[x]) return;
	vis[x] = 1;
	if(G[x].empty()) {
		a[x] = 1;
		return;
	}
	priority_queue<int> q;
	
	for(int y : G[x]) {
		dfs1(y);
		q.push(a[y]);
	}
	int v1 = q.top(); q.pop();
	int v2 = q.top(); q.pop();
	a[x] = v1 + v2;
}
signed main() {
	NOSYNC;
	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];
		++ d[y]; ++ d[z];
	}
	
	queue<int> q;
	for(int i = 1; i <= n; i ++) {
		if(!d[i]) {
			q.push(i);
		}
	}
	
	while(!q.empty()) {
		int u = q.front(); q.pop();
		vis[u] = 1;
		for(int v : G[u]) {
			-- d[v];
			if(!d[v]) {
				q.push(v);
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		if(!vis[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	
	for(int i = 1; i <= n; i ++) vis[i] = 0;
	
	for(int i = 1; i <= n; i ++) {
		if(!in[i] && !vis[i]) dfs1(i);
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		ans += a[i];
	}
	
	if(ans > 1e9) {
		cout << -1 << endl;
		return 0;
	}
	
	cout << ans << endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 11828kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

score: 0
Accepted
time: 4ms
memory: 12216kb

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

input:

5 2
1 2 3
2 3 4

output:

8

result:

ok 1 number(s): "8"

Test #11:

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

input:

10 1
1 2 3

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

10 1
1 2 2

output:

11

result:

ok 1 number(s): "11"

Test #13:

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

input:

10 2
1 2 3
2 3 4

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 4ms
memory: 12096kb

input:

10 2
1 2 2
2 3 4

output:

14

result:

ok 1 number(s): "14"

Test #15:

score: 0
Accepted
time: 4ms
memory: 13844kb

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: 0ms
memory: 14108kb

input:

20 1
1 2 2

output:

21

result:

ok 1 number(s): "21"

Test #17:

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

input:

20 2
1 2 3
2 3 3

output:

23

result:

ok 1 number(s): "23"

Test #18:

score: 0
Accepted
time: 4ms
memory: 11748kb

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

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: 4ms
memory: 13868kb

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: 0ms
memory: 12192kb

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: 0ms
memory: 13864kb

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

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: 0ms
memory: 13864kb

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

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

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: 0ms
memory: 13960kb

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

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:

-1

result:

ok 1 number(s): "-1"

Test #29:

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

input:

2000 321
542 97 1114
519 254 1751
1344 621 878
1701 682 1976
947 139 618
1930 986 1144
437 1803 1241
694 1316 1725
636 1886 1728
406 1435 453
530 802 1423
1575 1283 1451
64 982 536
990 123 1412
1 2 2
1013 1788 773
792 353 98
22 1024 1038
1169 1251 1780
2 3 4
573 1327 205
1575 102 474
420 717 451
84 ...

output:

12640161

result:

ok 1 number(s): "12640161"

Test #30:

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

input:

2000 401
1 2 3
1302 160 543
431 1432 1771
727 1624 144
1965 1363 365
360 1 1960
483 140 110
169 745 1102
608 917 1278
1258 1883 734
1855 748 1859
2 3 3
68 741 1342
1762 323 124
1686 1481 57
515 1497 699
1283 1923 1461
135 870 1705
1715 579 700
139 607 1680
58 550 1717
774 763 589
142 883 701
1982 83...

output:

52876268

result:

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