UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214285#2383. 期望直径nodgd0713ms13536kbC++113.3kb2024-11-16 22:57:462024-11-16 23:15:04

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;
const int P = 1000000007;

int N, M, Q, Ty;
int elast[MAX_N], ey[MAX_N << 1], enext[MAX_N << 1];
int gr[MAX_N], gsz[MAX_N], gmd[MAX_N];
vector<int> gc[MAX_N];
int dis[MAX_N], dis2[MAX_N];
map<pair<int,int>,int> ans;

void dfs(int u, int fa) {
    for (int j = elast[u], v; j; j = enext[j]) {
        if ((v = ey[j]) != fa) {
            dis2[v] = dis2[u] + 1;
            dfs(v, u);
        }
    }
}

void init(int st) {
    static int q[MAX_N], qh, qt;
    gr[st] = st;
    qh = 0, qt = 1, q[0] = st;
    while (qh != qt) {
        int u = q[qh ++];
        for (int j = elast[u], v; j; j = enext[j]) {
            if (!gr[v = ey[j]]) {
                dis[v] = dis[u] + 1;
                gr[v] = st;
                q[qt ++] = v;
            }
        }
    }
    int A = q[qt - 1];
    for (int i = 0; i < qt; i ++) {
        gr[q[i]] = 0;
        dis[q[i]] = 0;
    }
    gr[A] = st;
    qh = 0, qt = 1, q[0] = A;
    while (qh != qt) {
        int u = q[qh ++];
        for (int j = elast[u], v; j; j = enext[j]) {
            if (!gr[v = ey[j]]) {
                dis[v] = dis[u] + 1;
                gr[v] = st;
                q[qt ++] = v;
            }
        }
    }
    int B = q[qt - 1];
    gsz[st] = qt;
    gmd[st] = dis[B];
    gc[st].resize(dis[B] + 1, 0);
    dfs(B, 0);
    for (int i = 0; i < qt; i ++) {
        int u = q[i];
        int d = max(dis[u], dis2[u]);
        gc[st][d] ++;
    }
    // printf("st=%d, c=", st);
    // for (int d = 0; d <= gmd[st]; d ++) {
    //     printf("%d,", gc[st][d]);
    // }
    // printf("\n");
}

int power_mod(int a, int b) {
    int c = 1;
    for (; b; b >>= 1) {
        if (b & 1) c = 1ll * c * a % P;
        a = 1ll * a * a % P;
    }
    return c;
}

int main() {
    scanf("%d%d%d%d", &N, &M, &Q, &Ty);
    for (int i = 1, j = 1; i <= M; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        ey[j] = y, enext[j] = elast[x], elast[x] = j ++;
        ey[j] = x, enext[j] = elast[y], elast[y] = j ++;
    }
    for (int i = 1; i <= N; i ++) {
        if (!gr[i]) init(i);
    }
    for (int i = 1; i <= Q; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (gr[x] == gr[y]) {
            printf("-1\n");
        } else {
            x = gr[x], y = gr[y];
            if (gmd[x] < gmd[y]) swap(x, y);
            if (ans.count(make_pair(x, y))) {
                printf("%d\n", ans[make_pair(x, y)]);
            } else {
                int Dx = gmd[x], Dy = gmd[y];
                auto &cx = gc[x], &cy = gc[y];
                int res = 0;
                for (int d = Dx + 1; d <= Dx + Dy; d ++) {
                    long long t = 0;
                    for (int d2 = 0; d2 <= d && d2 <= Dy; d2 ++) {
                        t += 1ll * cx[d - d2] * cy[d2];
                    }
                    res = (res + t % P * (d - Dx)) % P;
                }
                int res_ = power_mod(1ll * gsz[x] * gsz[y] % P, P - 2);
                res = 1ll * res * res_ % P;
                res += Dx + 1;
                printf("%d\n", res);
                ans[make_pair(x, y)] = res;
            }
        }
    }
    return 0;
}
Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3612kb

input:

30 15 30 0
2 5
6 25
22 21
7 9
7 22
22 24
27 26
12 22
28 27
27 9
8 1
29 6
20 18
28 16
20 23
23 9
1 10...

output:

66666675
2
3
7
66666675
7
666666675
7
800000013
1
7
3
2
800000013
-1
7
7
7
1
2
2
7
1
7
1
800000013
3...

result:

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

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3612kb

input:

30 15 30 0
18 29
3 22
14 2
25 5
19 24
27 9
2 5
30 10
22 10
7 29
28 11
20 16
3 19
5 1
10 15
18 8
27 1...

output:

3
428571438
200000006
800000019
6
4
6
6
800000019
428571438
3
47619058
200000006
4
-1
2
666666675
6
...

result:

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

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3620kb

input:

80 40 80 0
50 4
11 44
10 39
62 34
69 67
66 17
67 19
66 45
11 22
62 14
54 31
9 18
49 52
44 57
63 80
1...

output:

1
352941202
23
23
23
1
1
23
352941202
23
666666675
1
23
23
2
352941202
23
1
1
23
23
1
23
1
3
1
2
23
...

result:

wrong answer 2nd lines differ - expected: '58823552', found: '352941202'

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 3620kb

input:

80 40 80 0
77 43
64 28
18 16
25 47
78 8
48 78
6 31
51 76
45 4
79 50
29 41
9 45
69 21
41 46
70 34
74 ...

output:

5
1
962962979
6
977777801
119047637
977777801
6
6
6
866666678
1
6
1
5
4
416666674
2
3
3
1
6
5
977777...

result:

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

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

80 40 80 0
56 60
73 50
72 62
53 17
1 60
27 5
75 40
30 10
18 53
19 79
53 28
19 38
40 42
61 6
2 16
1 5...

output:

3
2
7
1
2
9
1
66666675
7
277777792
1
166666673
388888901
166666673
3
1
2
833333346
800000013
3888889...

result:

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

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

80 40 80 0
53 55
50 22
3 75
77 2
70 48
23 59
54 41
67 60
33 76
40 7
9 5
66 32
49 80
41 70
40 19
57 3...

output:

6
9
90909100
666666675
9
6
1
200000006
606060618
2
1
2
428571438
9
1
7
9
800000019
454545465
1666666...

result:

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

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3636kb

input:

300 150 300 0
283 279
218 235
125 184
262 180
143 229
175 179
138 275
285 182
253 26
143 141
28 30
9...

output:

450980405
152941201
636363650
16
16
1
3
1
562500020
309090924
3
1
933333349
2
666666675
320312519
1
...

result:

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

Test #8:

score: 0
Wrong Answer
time: 2ms
memory: 3636kb

input:

300 150 300 0
259 289
214 108
213 200
11 217
204 152
162 40
25 54
25 115
286 158
53 123
213 30
268 2...

output:

2
4
3
15
3
109709994
1
3
3
377049203
20
3
2
20
200000006
3
377049203
377049203
666666675
2
15
333333...

result:

wrong answer 2nd lines differ - expected: '500000007', found: '4'

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 3624kb

input:

300 297 300 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
1...

output:

806054291
43157910
43157910
43157910
43157910
806054291
43157910
649097723
806054291
649097723
80605...

result:

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

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 3620kb

input:

300 297 300 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
1...

output:

488859199
611147838
611147838
611147838
611147838
488859199
611147838
941352927
488859199
941352927
...

result:

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

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 3668kb

input:

1000 997 1000 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18...

output:

511943357
781790891
781790891
781790891
781790891
511943357
781790891
494571641
511943357
494571641
...

result:

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

Test #12:

score: 0
Wrong Answer
time: 0ms
memory: 3712kb

input:

1000 500 1000 0
951 746
924 806
141 768
702 327
917 566
465 127
89 896
587 605
10 703
444 931
867 40...

output:

496633046
29
1
12
55555580
533333344
142857158
29
666666675
2
4
2
1
14
979338879
17
750000009
3
1
31...

result:

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

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 3708kb

input:

1000 500 1000 0
284 587
979 855
443 39
216 126
410 581
591 137
100 376
244 622
277 957
128 341
536 3...

output:

4
2
1
3
454545465
90909098
500000008
2
755555578
285714293
4
16
1
2
6
4
16
4
16
633333352
2
1
327272...

result:

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

Test #14:

score: 0
Wrong Answer
time: 156ms
memory: 8716kb

input:

100000 99597 100000 0
44158 25720
25720 84658
84658 90057
90057 99607
99607 50202
50202 18449
18449 ...

output:

807736762
354134452
907705027
820823825
881199670
601032824
586189343
255984221
666345798
926084031
...

result:

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

Test #15:

score: 0
Wrong Answer
time: 222ms
memory: 8452kb

input:

100000 99597 100000 0
79104 47592
47592 20172
20172 51655
51655 42698
42698 2208
2208 50026
50026 31...

output:

95850273
365708663
305725533
793908870
327555502
466458670
401149074
343688280
463972398
686450149
9...

result:

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

Test #16:

score: 0
Wrong Answer
time: 73ms
memory: 8836kb

input:

100000 89998 100000 1
1 2
1 3
3 4
1 5
6 7
6 8
6 9
6 10
11 12
12 13
11 14
11 15
16 17
17 18
18 19
19 ...

output:

660259621
660259621
192247537
660259621
192247537
660259621
660259621
192247537
660259621
660259621
...

result:

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

Test #17:

score: 0
Wrong Answer
time: 132ms
memory: 13536kb

input:

100000 99000 100000 1
1 2
1 3
3 4
1 5
2 6
3 7
3 8
5 9
7 10
2 11
6 12
1 13
13 14
10 15
12 16
12 17
17...

output:

-1
283600029
84100028
919100034
241700027
666300035
774700031
140700025
196300032
446300033
47370003...

result:

wrong answer 2nd lines differ - expected: '300000025', found: '283600029'

Test #18:

score: 0
Wrong Answer
time: 128ms
memory: 13536kb

input:

100000 99000 100000 1
1 2
1 3
3 4
1 5
2 6
3 7
3 8
5 9
7 10
2 11
6 12
1 13
13 14
10 15
12 16
12 17
17...

output:

-1
283600029
84100028
919100034
241700027
666300035
774700031
140700025
196300032
446300033
47370003...

result:

wrong answer 2nd lines differ - expected: '300000025', found: '283600029'

Test #19:

score: 0
Runtime Error

input:

100000 99997 100000 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17...

output:

result:

Test #20:

score: 0
Runtime Error

input:

100000 99997 100000 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17...

output:

result:

中文 English

Server time: 2024-12-02 07:38:26 | 开源项目