QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416031#5403. 树数术fairyqq280 0ms0kbC++143.7kb2024-05-21 14:59:392024-05-21 14:59:41

Judging History

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

  • [2024-05-21 14:59:41]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-05-21 14:59:39]
  • 提交

answer

// #pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define per(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
typedef pair<int, int> pii;
const int N = 700010;
char buf[1<<20], *p1, *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<20, stdin), p1==p2)?0:*p1++)
int read(){
    int ret = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) ret = (ret<<1)+(ret<<3)+(c^48), c = getchar();
    return ret;
}
int stk[15], top;
void print(int x){
    do stk[++top] = x % 10, x /= 10; while(x);
    while(top) putchar(stk[top] ^ 48), top--;
    putchar('\n');
}
int a[N], dep[N];

int lca(int x, int y);
namespace TREE{
    int lc[N<<2];
    vector<int> t[N<<2];
    void build(int u, int l, int r){
        if(l == r) {t[u] = {a[l]}, lc[u] = a[l]; return;}
        int mid = (l + r) >> 1;
        build(ls, l, mid); build(rs, mid + 1, r);
        t[u] = t[ls];
        int tmp = lca(lc[ls], t[rs].front());
        for(int &i : t[rs]) if(dep[i] <= dep[tmp]) t[u].push_back(i);
        lc[u] = lca(lc[ls], lc[rs]);
    }
    pii calc(int u, int id){
        // if(!~id) printf("%d %d %d\n", u, id, t[u].size());
        if(!~id) return make_pair(lc[u], t[u].size());
        id = lca(id, t[u].front());
        int l = 0, r = t[u].size() - 1, ret = t[u].size();
        while(l <= r){
            int mid = (l + r) >> 1;
            if(dep[t[u][mid]] <= dep[id]) ret = mid, r = mid - 1;
            else l = mid + 1;
        }
        // printf("%d %d %d\n", u, id, t[u].size() - ret);
        return make_pair(lca(id, lc[u]), t[u].size() - ret);
    }
    // return pair<int, int> (the id of min dep, cnt)
    pii query(int u, int l, int r, int x, int y, int id){  
        // if(x <= l && r <= y) printf("query: %d %d %d\n", u, l, r);
        if(x <= l && r <= y) return calc(u, id);
        // if(l == r) return calc(u, id);
        int cnt = 0, mid = (l + r) >> 1;
        if(x <= mid){
            pii tmp = query(ls, l, mid, x, y, id);
            id = tmp.first; cnt += tmp.second;
        }
        if(y > mid){
            pii tmp = query(rs, mid + 1, r, x, y, id);
            id = tmp.first; cnt += tmp.second;
        }
        return make_pair(id, cnt);
    }
}
using TREE::build; using TREE::query;

int st[N<<1][21], blg[N], tot;
vector<int> e[N];
void dfs(int x, int F){
    dep[x] = dep[F] + 1;
    st[++tot][0] = x; blg[x] = tot;
    for(int &y : e[x]) if(y ^ F) dfs(y, x), st[++tot][0] = x;
}
void st_init(){
    rep(j, 1, 20) rep(i, 1, tot - (1<<j) + 1)
        if(dep[st[i][j-1]] < dep[st[i+(1<<(j-1))][j-1]])
            st[i][j] = st[i][j-1];
        else st[i][j] = st[i+(1<<(j-1))][j-1];
}
int lca(int x, int y){
    x = blg[x], y = blg[y];
    if(x > y) swap(x, y);
    int t = __lg(y - x + 1);
    if(dep[st[x][t]] < dep[st[y-(1<<t)+1][t]]) return st[x][t];
    else return st[y-(1<<t)+1][t];
}

int n, m, q;

int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    n = read(), m = read(), q = read();
    rep(i, 1, n - 1){
        int x = read(), y = read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    st_init();
    rep(i, 1, m) a[i] = read();
    build(1, 1, m);
    while(q--){
        int k = read(), id = -1, ans = 0;
        rep(i, 1, k){
            int x = read(); int y = read();
            pii tmp = query(1, 1, m, x, y, id);
            id = tmp.first; ans += tmp.second;
        }
        print(ans);
    }
    // cerr << "total time: " << (clock() * 1000 / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

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:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #2:

score: 0
Dangerous Syscalls

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:


result:


Subtask #3:

score: 0
Dangerous Syscalls

Test #3:

score: 0
Dangerous Syscalls

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:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%