QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#598186 | #6340. Tourism | Dimash# | 0 | 23ms | 14148kb | C++17 | 1.8kb | 2024-09-28 20:46:55 | 2024-09-28 20:46:55 |
Judging History
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%