QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604617#8760. 不等式xing4c#WA 3ms10740kbC++141.4kb2024-10-02 12:32:512024-10-02 12:32:51

Judging History

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

  • [2024-10-02 12:32:51]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:10740kb
  • [2024-10-02 12:32:51]
  • 提交

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'
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];
	}
	cout << ans << endl;
	return 0;
}

詳細信息

Test #1:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

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

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

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

input:

10 1
1 2 3

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

10 1
1 2 2

output:

11

result:

ok 1 number(s): "11"

Test #13:

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

input:

10 2
1 2 3
2 3 4

output:

13

result:

ok 1 number(s): "13"

Test #14:

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

input:

10 2
1 2 2
2 3 4

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

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

input:

20 1
1 2 2

output:

21

result:

ok 1 number(s): "21"

Test #17:

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

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

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: 2ms
memory: 10484kb

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: 2ms
memory: 10740kb

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

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

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: 2ms
memory: 8696kb

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

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

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

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

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

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:

-1053083736

result:

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