QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142212#1972. JJ RallyJoe_yue6WA 149ms189804kbC++142.9kb2023-08-18 17:31:182023-08-18 17:31:21

Judging History

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

  • [2023-08-18 17:31:21]
  • 评测
  • 测评结果:WA
  • 用时:149ms
  • 内存:189804kb
  • [2023-08-18 17:31:18]
  • 提交

answer

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
int const N = 1e3, M = 1048577, N1 = 20, M1 = 30;
int s[2], t[2], dis[M1]; //所有的点需要平移
struct stu1 {
	int x, y, w;
} ed[N];
struct stu2 {
	int y, nex, w;
} e[N * 2];
long long a[M1], g[2][M], lin[M1], cnt, tot, pw[M], n, m, f[M][N1]; //sosdp一下
int Get(int x, int s1, int t1) {
	if (x == s1) return n;
	if (x == t1) return n + 1;
	int y = lower_bound(a, a + cnt, x) - a; //从0开始
	if (x != a[y]) return n + 2;
	return y;
}
void work(int x, int y, int w) {
	e[++tot] = (stu2) {
		y, lin[x], w
	};
	lin[x] = tot;
}
bool fl[M1];
#define fi first
#define se second
int lb(int x) {
	return x & (-x);
}
void sol(int s1, int t1, int op) {
	if (s1 == t1) {
		g[op][0] = 1;
		return;
	}
	tot = 0;
	for (int i = 0; i <= n + 1; i++) lin[i] = 0, dis[i] = 1e9, fl[i] = 0; //一共是cnt个点
	int x, y, w;
	for (int i = 1; i <= m; i++) {
		x = ed[i].x;
		y = ed[i].y;
		w = ed[i].w;
		x = Get(x, s1, t1);
		y = Get(y, s1, t1);
		if (x == n + 2 || y == n + 2) continue;
		work(x, y, w);
		work(y, x, w);
	}
	dis[n] = 0;
	priority_queue<pair<int, int>> q;
	q.push(mp(0, n));
	while (q.size()) {
		x = q.top().se;
		q.pop();
		if (fl[x]) continue;
		fl[x] = 1;
		for (int i = lin[x]; i; i = e[i].nex) {
			y = e[i].y;
			if (dis[y] > dis[x] + e[i].w) {
				dis[y] = dis[x] + e[i].w;
				q.push(mp(-dis[y], y));
			}
		}
	}
	for (int i = lin[n]; i; i = e[i].nex) {
		y = e[i].y;
		if (e[i].w == dis[y]) {
			if (y == n + 1) {
				g[op][0]++;
				//cout<<"qwq"<<endl;
			} else f[1 << y][y]++;
		}
	}

	int w1;
	for (int i = 1; i < (1 << cnt); i++) {
		w1 = i;
		while (w1) {
			int j = pw[lb(w1)];
			w1 -= lb(w1);
			if (f[i][j]) {
				for (int k = lin[j]; k; k = e[k].nex) {
					y = e[k].y;
					w = e[k].w;
					if (dis[j] + w == dis[y]) {
						if (y == n + 1) g[op][i] += f[i][j];
						else f[(1 << y) | i][y] += f[i][j];
					}
				}
			}
		}
	}
	memset(f, 0, sizeof(f));
}
void pd() {
	if (s[0] == s[1] || t[0] == t[1] || s[0] == t[1] || s[1] == t[0]) {
		printf("%d", 0);
		exit(0);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int x, y, w;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &w);
		ed[i] = (stu1) {
			x, y, w
		};
	} //s=n点 t n+1点 [0,n-1]
	scanf("%d%d%d%d", &s[0], &t[0], &s[1], &t[1]);
	pd();
	for (int i = 1; i <= n; i++)
		if (i != s[0] && i != s[1] && i != t[0] && i != t[1]) a[cnt++] = i;
	for (int i = 0; i < cnt; i++) pw[1 << i] = i;
	sol(s[0], t[0], 0);
	sol(s[1], t[1], 1);

	int sum = (1 << cnt);

	for (int i = 0; i < cnt; i++) //sosdp
		for (int s = 0; s < sum; s++)
			if (s & (1 << i)) g[0][s] += g[0][s ^ (1 << i)];

	long long ans = 0;
	sum--;
//	cout<<g[0][0]<<endl;
	for (int s = 0; s <= sum; s++) {
		ans += 1ll * g[1][s] * g[0][sum ^ s];
	}
	printf("%lld", ans);
}

详细

Test #1:

score: 100
Accepted
time: 19ms
memory: 171544kb

input:

4 4
1 2 2
2 3 1
1 3 1
3 4 1
1 2 3 4

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 12ms
memory: 167928kb

input:

4 3
1 2 1
2 3 1
3 4 1
1 3 2 4

output:

0

result:

ok single line: '0'

Test #3:

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

input:

6 8
1 4 1
1 3 1
4 2 1
3 2 1
1 2 2
1 5 1
5 2 1
5 6 2
1 2 6 5

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 149ms
memory: 189804kb

input:

24 276
1 2 117
1 3 36
1 4 247
1 5 150
1 6 215
1 7 232
1 8 161
1 9 209
1 10 190
1 11 4
1 12 102
1 13 281
1 14 301
1 15 32
1 16 138
1 17 114
1 18 304
1 19 141
1 20 105
1 21 64
1 22 75
1 23 23
1 24 237
2 3 153
2 4 364
2 5 267
2 6 332
2 7 349
2 8 278
2 9 326
2 10 307
2 11 113
2 12 219
2 13 398
2 14 418
...

output:

3486784401

result:

ok single line: '3486784401'

Test #5:

score: 0
Accepted
time: 119ms
memory: 187700kb

input:

24 276
1 2 48
1 3 81
1 4 233
1 5 362
1 6 37
1 7 49
1 8 17
1 9 36
1 10 327
1 11 76
1 12 271
1 13 169
1 14 124
1 15 3
1 16 421
1 17 210
1 18 144
1 19 293
1 20 18
1 21 98
1 22 392
1 23 398
1 24 226
2 3 33
2 4 281
2 5 410
2 6 85
2 7 98
2 8 65
2 9 12
2 10 376
2 11 124
2 12 319
2 13 217
2 14 173
2 15 45
2...

output:

535122674

result:

ok single line: '535122674'

Test #6:

score: 0
Accepted
time: 56ms
memory: 180336kb

input:

23 253
1 2 365
1 3 199
1 4 169
1 5 70
1 6 36
1 7 2
1 8 119
1 9 387
1 10 383
1 11 140
1 12 138
1 13 318
1 14 94
1 15 326
1 16 84
1 17 239
1 18 160
1 19 45
1 20 250
1 21 283
1 22 17
1 23 116
2 3 166
2 4 196
2 5 295
2 6 329
2 7 367
2 8 246
2 9 22
2 10 18
2 11 226
2 12 228
2 13 47
2 14 271
2 15 39
2 16 ...

output:

190681453

result:

ok single line: '190681453'

Test #7:

score: 0
Accepted
time: 135ms
memory: 189600kb

input:

24 276
1 2 278
1 3 214
1 4 18
1 5 128
1 6 87
1 7 47
1 8 325
1 9 89
1 10 189
1 11 363
1 12 88
1 13 183
1 14 215
1 15 280
1 16 146
1 17 191
1 18 315
1 19 115
1 20 55
1 21 241
1 22 267
1 23 314
1 24 17
2 3 64
2 4 260
2 5 150
2 6 191
2 7 231
2 8 47
2 9 367
2 10 89
2 11 84
2 12 366
2 13 95
2 14 63
2 15 2...

output:

1719666670

result:

ok single line: '1719666670'

Test #8:

score: 0
Accepted
time: 36ms
memory: 170828kb

input:

20 190
1 2 35
1 3 74
1 4 11
1 5 152
1 6 147
1 7 225
1 8 46
1 9 65
1 10 311
1 11 242
1 12 189
1 13 115
1 14 346
1 15 64
1 16 276
1 17 13
1 18 217
1 19 196
1 20 31
2 3 39
2 4 24
2 5 117
2 6 112
2 7 190
2 8 81
2 9 30
2 10 276
2 11 207
2 12 154
2 13 80
2 14 311
2 15 99
2 16 241
2 17 48
2 18 182
2 19 161...

output:

29733571

result:

ok single line: '29733571'

Test #9:

score: 0
Accepted
time: 21ms
memory: 170048kb

input:

19 171
1 2 87
1 3 130
1 4 199
1 5 47
1 6 253
1 7 323
1 8 103
1 9 47
1 10 212
1 11 312
1 12 76
1 13 168
1 14 274
1 15 353
1 16 12
1 17 205
1 18 169
1 19 34
2 3 42
2 4 113
2 5 134
2 6 166
2 7 236
2 8 16
2 9 40
2 10 125
2 11 226
2 12 163
2 13 81
2 14 188
2 15 267
2 16 99
2 17 117
2 18 82
2 19 53
3 4 70...

output:

3711731

result:

ok single line: '3711731'

Test #10:

score: 0
Accepted
time: 70ms
memory: 180248kb

input:

23 253
1 2 123
1 3 203
1 4 83
1 5 73
1 6 128
1 7 191
1 8 139
1 9 261
1 10 233
1 11 180
1 12 27
1 13 205
1 14 76
1 15 57
1 16 143
1 17 35
1 18 80
1 19 306
1 20 282
1 21 110
1 22 118
1 23 316
2 3 326
2 4 206
2 5 196
2 6 5
2 7 314
2 8 262
2 9 383
2 10 356
2 11 303
2 12 96
2 13 328
2 14 199
2 15 66
2 16...

output:

250401531

result:

ok single line: '250401531'

Test #11:

score: 0
Accepted
time: 20ms
memory: 169916kb

input:

4 6
1 2 47
1 3 88
1 4 21
2 3 41
2 4 26
3 4 67
3 2 4 1

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 16ms
memory: 170016kb

input:

5 10
1 2 36
1 3 52
1 4 23
1 5 20
2 3 16
2 4 13
2 5 16
3 4 29
3 5 32
4 5 3
4 5 3 1

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 21ms
memory: 170784kb

input:

6 15
1 2 36
1 3 66
1 4 90
1 5 77
1 6 47
2 3 30
2 4 54
2 5 41
2 6 11
3 4 24
3 5 11
3 6 19
4 5 13
4 6 43
5 6 30
1 3 5 6

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 24ms
memory: 171492kb

input:

7 21
1 2 37
1 3 51
1 4 41
1 5 3
1 6 2
1 7 16
2 3 14
2 4 78
2 5 34
2 6 35
2 7 21
3 4 92
3 5 48
3 6 49
3 7 35
4 5 44
4 6 43
4 7 57
5 6 1
5 7 13
6 7 14
5 2 1 7

output:

2

result:

ok single line: '2'

Test #15:

score: 0
Accepted
time: 20ms
memory: 171332kb

input:

8 28
1 2 117
1 3 23
1 4 111
1 5 34
1 6 57
1 7 106
1 8 65
2 3 94
2 4 6
2 5 151
2 6 60
2 7 11
2 8 52
3 4 88
3 5 57
3 6 34
3 7 83
3 8 42
4 5 145
4 6 54
4 7 5
4 8 46
5 6 91
5 7 140
5 8 99
6 7 49
6 8 8
7 8 41
8 2 3 7

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 20ms
memory: 170996kb

input:

9 36
1 2 145
1 3 17
1 4 32
1 5 67
1 6 81
1 7 114
1 8 18
1 9 109
2 3 162
2 4 113
2 5 78
2 6 64
2 7 31
2 8 163
2 9 36
3 4 49
3 5 84
3 6 98
3 7 131
3 8 1
3 9 126
4 5 35
4 6 49
4 7 82
4 8 50
4 9 77
5 6 14
5 7 47
5 8 85
5 9 42
6 7 33
6 8 99
6 9 28
7 8 132
7 9 5
8 9 127
7 8 5 2

output:

72

result:

ok single line: '72'

Test #17:

score: 0
Accepted
time: 12ms
memory: 170760kb

input:

10 45
1 2 37
1 3 96
1 4 134
1 5 75
1 6 57
1 7 121
1 8 79
1 9 39
1 10 66
2 3 133
2 4 171
2 5 38
2 6 94
2 7 158
2 8 116
2 9 76
2 10 103
3 4 38
3 5 171
3 6 39
3 7 25
3 8 17
3 9 57
3 10 30
4 5 209
4 6 77
4 7 13
4 8 55
4 9 95
4 10 68
5 6 132
5 7 196
5 8 154
5 9 114
5 10 141
6 7 64
6 8 22
6 9 18
6 10 9
7 ...

output:

36

result:

ok single line: '36'

Test #18:

score: 0
Accepted
time: 16ms
memory: 170760kb

input:

11 55
1 2 24
1 3 32
1 4 75
1 5 53
1 6 13
1 7 49
1 8 134
1 9 158
1 10 74
1 11 100
2 3 8
2 4 51
2 5 29
2 6 11
2 7 25
2 8 110
2 9 134
2 10 50
2 11 76
3 4 43
3 5 21
3 6 19
3 7 17
3 8 102
3 9 126
3 10 42
3 11 68
4 5 22
4 6 62
4 7 26
4 8 59
4 9 83
4 10 1
4 11 25
5 6 40
5 7 4
5 8 81
5 9 105
5 10 21
5 11 47...

output:

2

result:

ok single line: '2'

Test #19:

score: 0
Accepted
time: 20ms
memory: 171536kb

input:

12 66
1 2 14
1 3 72
1 4 27
1 5 42
1 6 35
1 7 41
1 8 148
1 9 20
1 10 95
1 11 144
1 12 126
2 3 58
2 4 13
2 5 56
2 6 49
2 7 27
2 8 134
2 9 34
2 10 81
2 11 130
2 12 112
3 4 45
3 5 114
3 6 107
3 7 31
3 8 76
3 9 92
3 10 23
3 11 72
3 12 54
4 5 69
4 6 62
4 7 14
4 8 121
4 9 47
4 10 68
4 11 117
4 12 99
5 6 7
...

output:

32

result:

ok single line: '32'

Test #20:

score: 0
Accepted
time: 11ms
memory: 169940kb

input:

13 78
1 2 131
1 3 89
1 4 199
1 5 118
1 6 31
1 7 148
1 8 34
1 9 14
1 10 162
1 11 60
1 12 61
1 13 48
2 3 42
2 4 68
2 5 13
2 6 162
2 7 17
2 8 97
2 9 117
2 10 31
2 11 191
2 12 192
2 13 83
3 4 110
3 5 29
3 6 120
3 7 59
3 8 55
3 9 75
3 10 73
3 11 149
3 12 150
3 13 41
4 5 81
4 6 230
4 7 51
4 8 165
4 9 185
...

output:

96

result:

ok single line: '96'

Test #21:

score: 0
Accepted
time: 15ms
memory: 170752kb

input:

14 91
1 2 60
1 3 38
1 4 76
1 5 6
1 6 36
1 7 65
1 8 208
1 9 55
1 10 183
1 11 149
1 12 135
1 13 94
1 14 91
2 3 98
2 4 136
2 5 54
2 6 24
2 7 5
2 8 268
2 9 115
2 10 243
2 11 209
2 12 195
2 13 154
2 14 31
3 4 38
3 5 44
3 6 74
3 7 103
3 8 170
3 9 17
3 10 145
3 11 111
3 12 97
3 13 56
3 14 129
4 5 82
4 6 11...

output:

432

result:

ok single line: '432'

Test #22:

score: 0
Accepted
time: 32ms
memory: 174344kb

input:

22 231
1 2 98
1 3 104
1 4 59
1 5 12
1 6 300
1 7 215
1 8 284
1 9 197
1 10 219
1 11 183
1 12 50
1 13 70
1 14 114
1 15 35
1 16 69
1 17 244
1 18 211
1 19 36
1 20 101
1 21 90
1 22 148
2 3 202
2 4 157
2 5 86
2 6 398
2 7 313
2 8 382
2 9 295
2 10 317
2 11 281
2 12 148
2 13 28
2 14 212
2 15 63
2 16 167
2 17 ...

output:

36

result:

ok single line: '36'

Test #23:

score: 0
Accepted
time: 44ms
memory: 180740kb

input:

23 253
1 2 285
1 3 105
1 4 161
1 5 32
1 6 243
1 7 296
1 8 286
1 9 207
1 10 125
1 11 20
1 12 205
1 13 263
1 14 81
1 15 245
1 16 146
1 17 26
1 18 173
1 19 195
1 20 109
1 21 69
1 22 64
1 23 100
2 3 180
2 4 446
2 5 317
2 6 42
2 7 11
2 8 1
2 9 492
2 10 410
2 11 305
2 12 80
2 13 22
2 14 204
2 15 530
2 16 ...

output:

248832

result:

ok single line: '248832'

Test #24:

score: 0
Accepted
time: 77ms
memory: 189548kb

input:

24 276
1 2 144
1 3 208
1 4 277
1 5 375
1 6 446
1 7 118
1 8 91
1 9 177
1 10 335
1 11 166
1 12 237
1 13 368
1 14 40
1 15 182
1 16 306
1 17 38
1 18 87
1 19 409
1 20 58
1 21 48
1 22 312
1 23 59
1 24 346
2 3 64
2 4 133
2 5 231
2 6 302
2 7 26
2 8 235
2 9 33
2 10 191
2 11 22
2 12 93
2 13 224
2 14 104
2 15 ...

output:

663552

result:

ok single line: '663552'

Test #25:

score: 0
Accepted
time: 38ms
memory: 176656kb

input:

23 253
1 2 250
1 3 128
1 4 54
1 5 274
1 6 216
1 7 201
1 8 115
1 9 78
1 10 58
1 11 183
1 12 149
1 13 294
1 14 63
1 15 270
1 16 211
1 17 43
1 18 142
1 19 103
1 20 35
1 21 202
1 22 1
1 23 11
2 3 376
2 4 196
2 5 26
2 6 33
2 7 49
2 8 136
2 9 171
2 10 307
2 11 67
2 12 101
2 13 46
2 14 312
2 15 20
2 16 39
...

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 48ms
memory: 179568kb

input:

23 253
1 2 104
1 3 92
1 4 5
1 5 52
1 6 181
1 7 30
1 8 29
1 9 44
1 10 70
1 11 150
1 12 201
1 13 9
1 14 29
1 15 136
1 16 135
1 17 231
1 18 149
1 19 105
1 20 55
1 21 31
1 22 171
1 23 11
2 3 12
2 4 99
2 5 155
2 6 76
2 7 74
2 8 76
2 9 61
2 10 174
2 11 46
2 12 97
2 13 113
2 14 133
2 15 31
2 16 239
2 17 12...

output:

4080

result:

ok single line: '4080'

Test #27:

score: 0
Accepted
time: 33ms
memory: 176468kb

input:

23 253
1 2 3
1 3 2
1 4 2
1 5 2
1 6 3
1 7 3
1 8 1
1 9 1
1 10 1
1 11 2
1 12 3
1 13 3
1 14 2
1 15 1
1 16 1
1 17 3
1 18 3
1 19 2
1 20 2
1 21 3
1 22 2
1 23 3
2 3 3
2 4 1
2 5 2
2 6 2
2 7 2
2 8 1
2 9 1
2 10 3
2 11 1
2 12 3
2 13 2
2 14 2
2 15 3
2 16 1
2 17 3
2 18 2
2 19 1
2 20 3
2 21 3
2 22 1
2 23 2
3 4 1
3...

output:

4

result:

ok single line: '4'

Test #28:

score: -100
Wrong Answer
time: 19ms
memory: 170712kb

input:

6 15
1 2 1
1 3 3
1 4 2
1 5 1
1 6 1
2 3 2
2 4 1
2 5 2
2 6 1
3 4 3
3 5 3
3 6 1
4 5 3
4 6 1
5 6 2
4 3 2 6

output:

1

result:

wrong answer 1st lines differ - expected: '0', found: '1'