QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#598186#6340. TourismDimash#0 23ms14148kbC++171.8kb2024-09-28 20:46:552024-09-28 20:46:55

Judging History

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

  • [2024-09-28 20:46:55]
  • 评测
  • 测评结果:0
  • 用时:23ms
  • 内存:14148kb
  • [2024-09-28 20:46:55]
  • 提交

answer

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;

const int l = 17;
int n, m, q, tin[N], tout[N], timer, dep[N], s[N], up[N][18];
vector<int> g[N];

void dfs(int v, int pr = 1) {
    tin[v] = ++timer;
    s[v] = 1;
    up[v][0] = pr;
    for(int i = 1; i < l; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]) {
        if(to != pr) {
            dep[to] = dep[v] + 1;
            dfs(to, v);
            s[v] += s[to];
        }
    }
    tout[v] = ++timer;
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v, int u) {
    if(is(v, u)) return v;
    if(is(u, v)) return u;
    for(int i = l - 1; i >= 0; i--) {
        if(!is(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
int  c[N];
void test() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dep[1] = 1;
    dfs(1);
    for(int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    for(int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        vector<int> t;
        for(int i = l; i <= r; i++) {
            t.push_back(c[i]);
        }
        sort(t.begin(), t.end(), [&](int x, int y) {
            return tin[x] < tin[y];
        });
        int res = dep[t[0]], v = t[0];
        for(int i = 1; i < (int)t.size(); i++) {
            res += dep[t[i]] - dep[lca(t[i - 1], t[i])];
            v = lca(v, t[i]);
        }
        cout << res - (n - s[v]) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

67
97
110
93
110
139
84
18
126
121
70
97
83
96
7
113
86
60
79
49
107
131
66
33
-31
41
86
110
55
123
46
130
73
63
93
75
113
85
25
95
127
69
85
121
77
127
123
83
34
62
99
121
57
50
99
106
22
69
127
42
74
134
68
94
-13
120
105
116
36
83
124
112
130
1
34
112
138
37
98
64
122
109
1
105
137
73
105
109
89
...

result:

wrong answer 8th numbers differ - expected: '24', found: '18'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #56:

score: 0
Time Limit Exceeded

input:

55321 88650 75523
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
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

55319
55319
55313
55306
55319
53676
55320
55301
55319
55319
55268
55319
55318
55320
55311
55311
55319
55275
55301
55319
55319
55317
55320
55319
55319
55318
55295
55318
55319
55319
55319
55248
55319
55320
55319
55319
55319
55319
55319
55319
55320
55301
55319
55186
55204
55320
55319
55319
55297
55318
...

result:


Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 23ms
memory: 14148kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

249
-957
-997
-981
267
-955
206
-929
157
214
-988
214
-939
-970
-980
195
-4906
-926
194
215
260
-970
-980
225
246
-992
-914
-1009
232
168
-4944
-4913
-989
-954
191
178
214
206
-1001
-956
-937
-951
-4829
312
197
-990
215
175
-935
-920
-1022
216
151
-967
224
-953
212
204
-992
-946
-918
188
-993
-1026
...

result:

wrong answer 1st numbers differ - expected: '276', found: '249'

Subtask #5:

score: 0
Time Limit Exceeded

Test #102:

score: 0
Time Limit Exceeded

input:

55965 89652 95687
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

42788
7820
39914
18090
47411
43990
2171
29300
18235
16451
44208
47526
32163
44460
32385
30155
45741
45708
47396
43518
30989
19208
13902
35077
49210
21200
43577
32110
19690
35461
45079
11601
42233
16862
23259
44558
41924
39465
34626
41081
32139
34482
41166
24623
11638
18786
29659
38064
42423
42321
30...

result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%