QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142210#1972. JJ RallyflameWA 157ms189908kbC++142.5kb2023-08-18 17:24:222023-08-18 17:24:24

Judging History

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

  • [2023-08-18 17:24:24]
  • 评测
  • 测评结果:WA
  • 用时:157ms
  • 内存:189908kb
  • [2023-08-18 17:24:22]
  • 提交

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: 22ms
memory: 170508kb

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: 22ms
memory: 168292kb

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: 23ms
memory: 170032kb

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

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: 125ms
memory: 188448kb

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: 54ms
memory: 182144kb

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: 131ms
memory: 189908kb

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: 20ms
memory: 171172kb

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

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: 80ms
memory: 182344kb

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: 13ms
memory: 170616kb

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: 12ms
memory: 169692kb

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: 18ms
memory: 170940kb

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: 27ms
memory: 170136kb

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: 12ms
memory: 171412kb

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: 19ms
memory: 171332kb

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: 24ms
memory: 171432kb

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: 21ms
memory: 171572kb

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: 15ms
memory: 170668kb

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: 23ms
memory: 170864kb

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: 20ms
memory: 170692kb

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: 28ms
memory: 176172kb

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: 59ms
memory: 180808kb

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: 66ms
memory: 187384kb

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: 32ms
memory: 177784kb

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: 42ms
memory: 178620kb

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: 48ms
memory: 176800kb

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: 16ms
memory: 170508kb

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'