oj.uz

Submission #953844

# Submission time Handle Problem Language Result Execution time Memory
953844 2024-03-26T17:58:32 Z dwuy Tourism (JOI23_tourism) C++14
28 / 100
 5000 ms 24660 KB 
/**   - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, m, q, bsz;
int c[MX], a[MX];
int answer[MX];
tpiii qr[MX];
vector<int> G[MX];

void nhap(){
    cin >> n >> m >> q;
    bsz = sqrt(m);
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1; i<=m; i++) cin >> c[i];
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        qr[i] = {l, r, i};
    }
}

struct Node{
    int cnt, sum;

    Node(){
        this->cnt = 0;
        this->sum = 0;
    }
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|3, Node());
    }

    void build(int l, int r, int id){
        if(l == r){
            tree[id].sum = 1;
            tree[id].cnt = 0;
            return;
        }
        int mid = (l + r)>>1;
        int ID = id<<1;
        build(l, mid, ID);
        build(mid+1, r, ID|1);
        tree[id].cnt = 0;
        tree[id].sum = tree[ID].sum + tree[ID|1].sum;
    }

    void build(){
        build(1, n, 1);
    }

    void update(int l, int r, int id, const int &u, const int &v, const int &val){
        if(l>v || r<u) return;
        if(l>=u && r<=v){
            tree[id].cnt += val;
            tree[id].sum = tree[id].cnt? 0 : l!=r? tree[id<<1].sum + tree[id<<1|1].sum : 1;
            return;
        }
        int mid = (l + r)>>1;
        int ID = id<<1;
        update(l, mid, ID, u, v, val);
        update(mid+1, r, ID|1, u, v, val);
        tree[id].sum = tree[id].cnt? 0 : tree[ID].sum + tree[ID|1].sum;
    }

    void update(int l, int r, int val){
        update(1, n, 1, l, r, val);
    }

    int get(int l, int r, int id, const int &u, const int &v){
        if(l>v || r<u) return 0;
        if(l>=u && r<=v) return tree[id].sum;
        int mid = (l+r)>>1;
        if(tree[id].cnt) return 0;
        return get(l, mid, id<<1, u, v) + get(mid+1, r, id<<1|1, u, v);
    }

    int get(int l, int r){
        return get(1, n, 1, l, r);
    }
};

namespace HLD{
    int p[MX];
    int h[MX];
    int num[MX];
    int head[MX];
    int numC[MX];
    int heavy[MX];
    SMT smt(0);

    void dfs(int u){
        h[u] = h[p[u]] + 1;
        heavy[u] = -1;
        for(int v: G[u]) if(v!=p[u]){
            p[v] = u;
            dfs(v);
            numC[u] += numC[v];
            if(heavy[u] == -1 || numC[v] > numC[heavy[u]]) heavy[u] = v;
        }
    }

    int dfsID = 0;
    void dcp(int u, int head){
        num[u] = ++dfsID;
        HLD::head[u] = head;
        if(heavy[u] != -1) dcp(heavy[u], head);
        for(int v: G[u]) if(HLD::head[v] == 0){
            dcp(v, v);
        }
    }

    void build(){
        dfs(1);
        dcp(1, 1);
        smt = SMT(n);
    }

    int LCA(int u, int v){
        if(u==0 || v==0) return max(u, v);
        while(head[u] != head[v]){
            if(h[head[u]] < h[head[v]]) swap(u, v);
            u = p[head[u]];
        }
        return h[u] < h[v]? u : v;
    }

    int get(int u, int v){
        int res = 0;
        if(u == 0) u = v;
        if(v == 0) v = u;
        int puv = LCA(u, v);
        while(head[u] != head[v]){
            if(h[head[u]] < h[head[v]]) swap(u, v);
            res += smt.get(num[head[u]], num[u]);
            u = p[head[u]];
        }
        if(h[u] > h[v]) swap(u, v);
        res += smt.get(num[u], num[v]);
        return res;
    }

    void update(int u, int v, int val){
        if(u == 0) u = v;
        if(v == 0) v = u;
        int puv = LCA(u, v);
        while(head[u] != head[v]){
            if(h[head[u]] < h[head[v]]) swap(u, v);
            smt.update(num[head[u]], num[u], val);
            u = p[head[u]];
        }
        if(h[u] > h[v]) swap(u, v);
        smt.update(num[u], num[v], val);
    }
}

bool comp(const tpiii &a, const tpiii &b){
    int l = get<0>(a), r = get<1>(a);
    int u = get<0>(b), v = get<1>(b);
    return l/bsz != u/bsz? l < u : r < v;
}

void solve(){
    HLD::build();
    sort(qr+1, qr+1+q, comp);
    for(int i=1, j=0, st=0, p=0, ans=0; i<=q; i++){
        int l, r, id;
        tie(l, r, id) = qr[i];
        if(i==1 || l/bsz != get<0>(qr[i-1])/bsz){
            HLD::smt.build();
            j = st = bsz*(l/bsz + 1);
            ans = 0;
            p = 0;
        }
        while(j<=r){
            ans += HLD::get(c[j], p);            
            HLD::update(c[j], p, 1);
            p = HLD::LCA(p, c[j]);
            j++;
        }

        vector<int> tmp;
        tmp.push_back(p);
        int result = ans;
        for(int t=l; t<min(r+1, st); t++){
            result += HLD::get(c[t], tmp.back());
            HLD::update(c[t], tmp.back(), 1);
            tmp.push_back(HLD::LCA(c[t], tmp.back()));
        }
        tmp.pop_back();
        for(int t=min(r, st-1); t>=l; t--){
            HLD::update(c[t], tmp.back(), -1);
            tmp.pop_back();
        }
        answer[id] = result;
    }

    for(int i=1; i<=q; i++) cout << answer[i] << endl;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Compilation message

tourism.cpp: In function 'long long int HLD::get(long long int, long long int)':
tourism.cpp:176:13: warning: unused variable 'puv' [-Wunused-variable]
  176 |         int puv = LCA(u, v);
      |             ^~~
tourism.cpp: In function 'void HLD::update(long long int, long long int, long long int)':
tourism.cpp:190:13: warning: unused variable 'puv' [-Wunused-variable]
  190 |         int puv = LCA(u, v);
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6692 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 4 ms 6704 KB Output is correct
10 Correct 4 ms 6492 KB Output is correct
11 Correct 3 ms 6496 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 3 ms 6488 KB Output is correct
14 Correct 4 ms 6616 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6492 KB Output is correct
17 Correct 3 ms 6704 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 3 ms 6492 KB Output is correct
20 Correct 3 ms 6488 KB Output is correct
21 Correct 3 ms 6492 KB Output is correct
22 Correct 3 ms 6492 KB Output is correct
23 Correct 3 ms 6704 KB Output is correct
24 Correct 3 ms 6492 KB Output is correct
25 Correct 3 ms 6704 KB Output is correct
26 Correct 3 ms 6496 KB Output is correct
27 Correct 2 ms 8664 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6692 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 4 ms 6704 KB Output is correct
10 Correct 4 ms 6492 KB Output is correct
11 Correct 3 ms 6496 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 3 ms 6488 KB Output is correct
14 Correct 4 ms 6616 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6492 KB Output is correct
17 Correct 3 ms 6704 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 3 ms 6492 KB Output is correct
20 Correct 3 ms 6488 KB Output is correct
21 Correct 3 ms 6492 KB Output is correct
22 Correct 3 ms 6492 KB Output is correct
23 Correct 3 ms 6704 KB Output is correct
24 Correct 3 ms 6492 KB Output is correct
25 Correct 3 ms 6704 KB Output is correct
26 Correct 3 ms 6496 KB Output is correct
27 Correct 2 ms 8664 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 37 ms 6884 KB Output is correct
31 Correct 53 ms 6896 KB Output is correct
32 Correct 63 ms 6984 KB Output is correct
33 Correct 60 ms 6748 KB Output is correct
34 Correct 59 ms 6980 KB Output is correct
35 Correct 38 ms 6972 KB Output is correct
36 Correct 41 ms 6984 KB Output is correct
37 Correct 49 ms 7008 KB Output is correct
38 Correct 21 ms 7008 KB Output is correct
39 Correct 28 ms 7004 KB Output is correct
40 Correct 20 ms 7084 KB Output is correct
41 Correct 11 ms 7000 KB Output is correct
42 Correct 10 ms 7100 KB Output is correct
43 Correct 19 ms 7004 KB Output is correct
44 Correct 65 ms 7008 KB Output is correct
45 Correct 62 ms 7004 KB Output is correct
46 Correct 38 ms 7004 KB Output is correct
47 Correct 31 ms 7008 KB Output is correct
48 Correct 32 ms 7256 KB Output is correct
49 Correct 32 ms 7004 KB Output is correct
50 Correct 32 ms 6964 KB Output is correct
51 Correct 32 ms 6968 KB Output is correct
52 Correct 29 ms 6748 KB Output is correct
53 Correct 29 ms 6744 KB Output is correct
54 Correct 29 ms 7004 KB Output is correct
55 Correct 29 ms 6748 KB Output is correct
56 Correct 5 ms 8536 KB Output is correct
57 Correct 3 ms 6748 KB Output is correct
58 Correct 4 ms 7004 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 4 ms 8708 KB Output is correct
4 Execution timed out 5051 ms 21332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 166 ms 16888 KB Output is correct
3 Correct 246 ms 17944 KB Output is correct
4 Correct 204 ms 18700 KB Output is correct
5 Correct 204 ms 23396 KB Output is correct
6 Correct 205 ms 23380 KB Output is correct
7 Correct 192 ms 23368 KB Output is correct
8 Correct 215 ms 23380 KB Output is correct
9 Correct 242 ms 23384 KB Output is correct
10 Correct 414 ms 23376 KB Output is correct
11 Correct 401 ms 23172 KB Output is correct
12 Correct 433 ms 23420 KB Output is correct
13 Correct 447 ms 23500 KB Output is correct
14 Correct 441 ms 23728 KB Output is correct
15 Correct 260 ms 24660 KB Output is correct
16 Correct 320 ms 23512 KB Output is correct
17 Correct 337 ms 23380 KB Output is correct
18 Correct 332 ms 23516 KB Output is correct
19 Correct 188 ms 22924 KB Output is correct
20 Correct 197 ms 22664 KB Output is correct
21 Correct 192 ms 22656 KB Output is correct
22 Correct 208 ms 22868 KB Output is correct
23 Correct 203 ms 22876 KB Output is correct
24 Correct 217 ms 22864 KB Output is correct
25 Correct 303 ms 22868 KB Output is correct
26 Correct 310 ms 22864 KB Output is correct
27 Correct 396 ms 22928 KB Output is correct
28 Correct 443 ms 22900 KB Output is correct
29 Correct 462 ms 22868 KB Output is correct
30 Correct 446 ms 23232 KB Output is correct
31 Correct 489 ms 23016 KB Output is correct
32 Correct 484 ms 23120 KB Output is correct
33 Correct 450 ms 23644 KB Output is correct
34 Correct 252 ms 24288 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 5 ms 8536 KB Output is correct
4 Execution timed out 5068 ms 18692 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6692 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 4 ms 6704 KB Output is correct
10 Correct 4 ms 6492 KB Output is correct
11 Correct 3 ms 6496 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 3 ms 6488 KB Output is correct
14 Correct 4 ms 6616 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6492 KB Output is correct
17 Correct 3 ms 6704 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 3 ms 6492 KB Output is correct
20 Correct 3 ms 6488 KB Output is correct
21 Correct 3 ms 6492 KB Output is correct
22 Correct 3 ms 6492 KB Output is correct
23 Correct 3 ms 6704 KB Output is correct
24 Correct 3 ms 6492 KB Output is correct
25 Correct 3 ms 6704 KB Output is correct
26 Correct 3 ms 6496 KB Output is correct
27 Correct 2 ms 8664 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 37 ms 6884 KB Output is correct
31 Correct 53 ms 6896 KB Output is correct
32 Correct 63 ms 6984 KB Output is correct
33 Correct 60 ms 6748 KB Output is correct
34 Correct 59 ms 6980 KB Output is correct
35 Correct 38 ms 6972 KB Output is correct
36 Correct 41 ms 6984 KB Output is correct
37 Correct 49 ms 7008 KB Output is correct
38 Correct 21 ms 7008 KB Output is correct
39 Correct 28 ms 7004 KB Output is correct
40 Correct 20 ms 7084 KB Output is correct
41 Correct 11 ms 7000 KB Output is correct
42 Correct 10 ms 7100 KB Output is correct
43 Correct 19 ms 7004 KB Output is correct
44 Correct 65 ms 7008 KB Output is correct
45 Correct 62 ms 7004 KB Output is correct
46 Correct 38 ms 7004 KB Output is correct
47 Correct 31 ms 7008 KB Output is correct
48 Correct 32 ms 7256 KB Output is correct
49 Correct 32 ms 7004 KB Output is correct
50 Correct 32 ms 6964 KB Output is correct
51 Correct 32 ms 6968 KB Output is correct
52 Correct 29 ms 6748 KB Output is correct
53 Correct 29 ms 6744 KB Output is correct
54 Correct 29 ms 7004 KB Output is correct
55 Correct 29 ms 6748 KB Output is correct
56 Correct 5 ms 8536 KB Output is correct
57 Correct 3 ms 6748 KB Output is correct
58 Correct 4 ms 7004 KB Output is correct
59 Correct 1 ms 6488 KB Output is correct
60 Correct 2 ms 8540 KB Output is correct
61 Correct 4 ms 8708 KB Output is correct
62 Execution timed out 5051 ms 21332 KB Time limit exceeded
63 Halted 0 ms 0 KB -