QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415979 | #5403. 树数术 | lqt1217 | 20 | 1265ms | 127968kb | C++14 | 1.7kb | 2024-05-21 13:24:11 | 2024-05-21 13:24:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> pii;
const int N= (int)1e6+ 5, M= N* 2;
int h[N], e[M], ne[M], idx;
int fa[N][21], l[N], r[N], tot, p[N];
pii a[N];
void add(int a, int b) {
e[idx]= b, ne[idx]= h[a], h[a]= idx++ ;
}
void dfs(int u, int f) {
l[u]= ++ tot;
for(int i= h[u]; ~i; i= ne[i]) {
int j= e[i];
if(j== f) continue;
dfs(j, u);
}
r[u]= tot;
}
int cl(int L, int R, int x) {
if(l[p[L]]<= x&& x<= r[p[L]]) return L;
for(int i= 20; i>= 0; i-- )
if(fa[L][i]&& (l[p[fa[L][i]]]> x|| r[p[fa[L][i]]]< x)) L= fa[L][i];
if(fa[L][0]> R) return 0;
return fa[L][0];
}
int main() {
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);
int n, m, q;
cin>> n>> m>> q;
memset(h, -1, sizeof h);
for(int i= 1; i< n; i++ ) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
for(int i= 1; i<= m; i++ )
scanf("%d", &p[i]);
dfs(1, -1);
for(int i= m- 1; i>= 1; i-- ) {
fa[i][0]= cl(i+ 1, m, l[p[i]]);
for(int j= 1; j<= 20; j++ )
fa[i][j]= fa[fa[i][j- 1]][j- 1];
}
while(q-- ) {
int k;
scanf("%d", &k);
for(int i= 1; i<= k; i++ )
scanf("%d%d", &a[i].fi, &a[i].se);
sort(a+ 1, a+ k+ 1);
int lst= 0, cnt= 0;
for(int i= 1; i<= k; i++ ) {
int st= (i== 1? a[i].fi: cl(a[i].fi, a[i].se, lst));
if(! (a[i].fi<= st&& st<= a[i].se)) continue;
cnt++ ;
for(int j= 20; j>= 0; j-- )
if(fa[st][j]&& fa[st][j]<= a[i].se) cnt+= (1<< j), st= fa[st][j];
lst= l[p[st]];
}
printf("%d\n", cnt);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1265ms
memory: 127968kb
input:
699990 699995 233333 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...
output:
414919 464289 494925 386270 442147 364276 401975 454211 431471 299450 366103 265439 325816 163975 348433 216139 401719 16634 200359 27351 103756 169847 290266 463858 339876 150935 151290 229206 198892 444771 398455 419146 293826 372006 432125 80459 385306 415228 62365 222331 474164 276309 284536 238...
result:
wrong answer 1st lines differ - expected: '121987', found: '414919'
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 1002ms
memory: 105244kb
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
211594 160846 176729 128251 32662 70710 74884 9095 68282 91324 154262 24279 31878 173468 75265 139715 91660 87525 194302 16875 81535 172911 29145 20483 151883 5255 9548 58890 38076 94152 14358 74859 48870 23981 41390 60976 13795 125823 427 26641 130620 174231 73241 55291 2364 78864 23391 4866 36002 ...
result:
ok 699992 lines
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 78ms
memory: 21696kb
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
9733 11330 8403 5136 22207 23231 12686 27288 23739 20937 18153 16379 8991 14036 11669 14685 20272 18955 21680 7927 21383 23576 14834 5714 15707 10013 7905 13254 13883 10446 16140 16796 11009 11912 15761 20419 11157 12192 14327 18260 19095 5239 4114 16522 7412 5005 16844 8747 19377 22600 12023 9161 9...
result:
wrong answer 9127th lines differ - expected: '19474', found: '19477'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%