ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215254 | #2437. 随机游走 | nodgd | 100 | 617ms | 14988kb | C++11 | 2.1kb | 2024-11-27 20:30:59 | 2024-11-27 23:38:23 |
answer
#include <bits/stdc++.h>
using namespace std;
const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline int read_int() {
int x = 0;
char ch = read_char(), flag = 0;
while (ch != '-' && (ch < '0' || ch > '9')) {
ch = read_char();
}
if (ch == '-') {
flag = 1;
ch = read_char();
}
for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
x = x * 10 + (ch - '0');
}
return flag ? -x : x;
}
const int MAX_N = 500000 + 5;
typedef long long i64;
int N, M;
int fath[MAX_N], dis[MAX_N], odd[MAX_N];
i64 SUM, sum[MAX_N];
double ans[MAX_N];
int get_fath(int i) {
if (fath[i] != i) {
int f = get_fath(fath[i]);
dis[i] ^= dis[fath[i]];
fath[i] = f;
}
return fath[i];
}
int main() {
N = read_int(), M = read_int();
int s = read_int();
for (int i = 1; i <= N; i ++) {
fath[i] = i, dis[i] = 0;
}
for (int i = 1; i <= M; i ++) {
int x = read_int(), y = read_int(), w = read_int();
sum[x] += w;
sum[y] += w;
int fx = get_fath(x), fy = get_fath(y);
if (fx != fy) {
fath[fx] = fy;
dis[fx] = dis[x] ^ dis[y] ^ 1;
odd[fy] |= odd[fx];
} else {
odd[fx] |= dis[x] ^ dis[y] ^ 1;
}
}
int fs = get_fath(s);
for (int i = 1; i <= N; i ++) {
if (get_fath(i) == fs) {
SUM += sum[i];
}
}
if (odd[fs]) {
double t = 1.0 / SUM;
for (int i = 1; i <= N; i ++) {
if (get_fath(i) == fs) {
ans[i] = sum[i] * t;
}
}
} else {
double t = 2.0 / SUM;
for (int i = 1; i <= N; i ++) {
if (get_fath(i) == fs && dis[i] == dis[s]) {
ans[i] = sum[i] * t;
}
}
}
for (int i = 1; i <= N; i ++) {
printf("%.10lf%c", ans[i], i < N ? ' ' : '\n');
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
2 2 1 1 2 552418 2 1 687983
output:
1.0000000000 0.0000000000
result:
ok 2 numbers
Test #2:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
15 20 6 1 4 828 2 4 337 3 14 927 5 8 390 6 3 646 7 4 48 9 5 349 10 4 485 11 4 620 12 4 276 13 4 714 ...
output:
0.0879033855 0.0333597307 0.0000000000 0.0000000000 0.0000000000 0.0639477331 0.0929518907 0.0386062...
result:
ok 15 numbers
Test #3:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
20 20 14 1 19 1746 2 17 3922 3 7 5216 4 18 5768 5 19 4 6 16 5240 8 14 7366 9 8 4420 10 20 8517 11 9 ...
output:
0.1317556522 0.0000000000 0.0000000000 0.0000000000 0.0000502980 0.1327993361 0.1483665719 0.0000000...
result:
ok 20 numbers
Test #4:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
60 100 40 1 43 752739 2 1 861767 3 21 651385 4 28 364 5 58 949 6 15 267 7 57 247988 8 50 820601 9 14...
output:
0.0267208176 0.0280196811 0.0107934158 0.0000165339 0.0098863016 0.0000044190 0.0420015432 0.0135919...
result:
ok 60 numbers
Test #5:
score: 10
Accepted
time: 0ms
memory: 1204kb
input:
98 100 53 1 27 986351 2 56 454750 3 36 141367 4 56 344982 5 70 727802 6 24 509565 7 55 776053 8 59 3...
output:
0.0000000000 0.0087000003 0.0000000000 0.0065999857 0.0139238651 0.0097486876 0.0148469738 0.0155966...
result:
ok 98 numbers
Test #6:
score: 10
Accepted
time: 0ms
memory: 1240kb
input:
817 1926 733 1 629 1 2 215 1 3 248 1 4 130 1 5 469 1 6 682 1 7 776 1 8 110 1 9 415 1 10 321 1 11 303...
output:
0.0010384216 0.0015576324 0.0010384216 0.0018172378 0.0023364486 0.0012980270 0.0007788162 0.0015576...
result:
ok 817 numbers
Test #7:
score: 10
Accepted
time: 80ms
memory: 6784kb
input:
166666 300000 119635 1 91644 655718 2 54315 300393 3 112333 880100 4 3430 427450 5 127315 74466 6 95...
output:
0.0000112198 0.0000020028 0.0000127108 0.0000028500 0.0000052638 0.0000034816 0.0000056758 0.0000050...
result:
ok 166666 numbers
Test #8:
score: 10
Accepted
time: 131ms
memory: 13168kb
input:
400000 500000 363488 1 254054 843859 2 169299 701504 3 174552 479095 4 70702 852271 5 301016 4 6 830...
output:
0.0000031258 0.0000044913 0.0000046792 0.0000023619 0.0000000000 0.0000005829 0.0000031231 0.0000048...
result:
ok 400000 numbers
Test #9:
score: 10
Accepted
time: 189ms
memory: 12008kb
input:
500000 500000 342024 1 367282 471300 2 346217 948546 3 230072 336639 4 458846 88399 5 20450 217996 6...
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000...
result:
ok 500000 numbers
Test #10:
score: 10
Accepted
time: 217ms
memory: 14988kb
input:
466666 500000 456939 1 304818 887447 2 55736 302299 3 283098 150863 4 424825 796422 5 99211 331398 6...
output:
0.0000052835 0.0000040518 0.0000005265 0.0000034901 0.0000047797 0.0000000000 0.0000020424 0.0000000...
result:
ok 466666 numbers