QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212755#1972. JJ Rallyucup-team1004WA 101ms20128kbC++141.6kb2023-10-13 20:21:582023-10-13 20:21:58

Judging History

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

  • [2023-10-13 20:21:58]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:20128kb
  • [2023-10-13 20:21:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=30,M=1<<20;
int n,m,a[N][N],d[N][N];
int s1,t1,s2,t2,vis[N],id[N];
ll g[M],h[M];
void dfs(ll *f,int u,int t,int S=0){
	// debug(u,t);
	for(int v=1;v<=n;v++){
		if(!a[u][v]||a[u][v]+d[v][t]>d[u][t])continue;
		if(v==t){
			f[S]++;
		}else if(!vis[v]){
			dfs(f,v,t,S|(1<<id[v]));
		}
	}
}
int main(){
	cin>>n>>m;
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=n;i++)d[i][i]=0;
	for(int u,v,w;m--;){
		cin>>u>>v>>w;
		a[u][v]=a[v][u]=w;
		d[u][v]=d[v][u]=w;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	cin>>s1>>t1>>s2>>t2;
	vis[s1]=vis[t1]=vis[s2]=vis[t2]=1;
	for(int i=1,k=0;i<=n;i++){
		if(!vis[i])id[i]=k++;
		else id[i]=-1;
	}
	dfs(g,s1,t1),dfs(h,s2,t2);
	int U=(1<<n-4)-1;
	for(int len=1;len<U;len<<=1){
		for(int i=0;i<=U;i+=len<<1){
			for(int j=0;j<len;j++){
				g[i|j]+=g[i|j|len],h[i|j]+=h[i|j|len];
			}
		}
	}
	for(int S=0;S<=U;S++)g[S]*=h[S];
	for(int len=1;len<U;len<<=1){
		for(int i=0;i<=U;i+=len<<1){
			for(int j=0;j<len;j++){
				g[i|j]-=g[i|j|len];
			}
		}
	}
	cout<<g[0]<<endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5636kb

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

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: 1ms
memory: 5736kb

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: 101ms
memory: 20128kb

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: 88ms
memory: 20096kb

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: 37ms
memory: 15060kb

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: 89ms
memory: 20092kb

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

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

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: 45ms
memory: 15236kb

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: 1ms
memory: 5780kb

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: -100
Wrong Answer
time: 1ms
memory: 5792kb

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:

1

result:

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