UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215254#2437. 随机游走nodgd100617ms14988kbC++112.1kb2024-11-27 20:30:592024-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