oj.uz

Submission #1037845

# Submission time Handle Problem Language Result Execution time Memory
1037845 2024-07-29T09:07:48 Z 김은성(#10980) Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 12548 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[100009];
int par[100009], val[100009], ans[100009], depth[100009];
int tree[1<<18];
int a[100009], cur[100009], cnt = 0;
const int buc = 3;
struct Query{
    int idx, l, r;
    bool operator<(Query &q){
        if(l/buc == q.l/buc)
            return r < q.r;
        return l < q.l;
    }
};
void dfs(int v){
    //printf("v=%d\n", v);
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i];
        if(u != par[v]){
            par[u] = v;
            depth[u] = depth[v] + 1;
            dfs(u);
        }
    }
}
int lca(int u, int v){
    if(u==-1)
        return v;
    if(v==-1)
        return u;
   // printf("init u=%d v=%d du=%d dv=%d\n", u, v,depth[u], depth[v]);
    if(depth[u] > depth[v])
        swap(u, v);
   // printf("middle u=%d v=%d\n", u, v);
    while(depth[u] < depth[v])
        v = par[v];
   // printf("u=%d v=%d\n", u, v);
    while(u != v){
        u = par[u];
        v = par[v];
    }
    return v;
}
void settree(int v, int l, int r){
    if(l==r)
        tree[v] = a[l];
    else{
        int mid = (l+r)/2;
        settree(2*v, l, mid);
        settree(2*v+1, mid+1, r);
        tree[v] = lca(tree[2*v], tree[2*v+1]);
    }
}
int query(int v, int l, int r, int s, int e){
    if(s<=l && r<=e)
        return tree[v];
    if(e<l || r<s)
        return -1;
    int mid = (l+r)/2;
    return lca(query(2*v, l, mid, s, e), query(2*v+1, mid+1, r, s, e));
}
void update(int v, int val){
    while(v){
        if(val==1 && cur[v] == 0)
            cnt++;
        else if(val==-1 && cur[v]==1)
            cnt--;
        cur[v] += val;
        v = par[v];
    }
}
int main(){
    int n, m, q, i, u, v;
    scanf("%d %d %d", &n, &m, &q);
    for(i=0; i<n-1; i++){
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(i=1; i<=m; i++){
        scanf("%d", &a[i]);
    }
    dfs(1);
    settree(1, 1, m);
    vector<Query> qu;
    for(i=0; i<q; i++){
        scanf("%d %d", &u, &v);
        qu.push_back({i, u, v});
        //printf("lca=%d\n", query(1, 1, m, u, v));
        ans[i] = -depth[query(1, 1, m, u, v)];
    }
    sort(qu.begin(), qu.end());
    int curl = 1, curr = 0;
    for(i=0; i<q; i++){
        int l = qu[i].l, r = qu[i].r;
        while(curr < r){
            update(a[++curr], 1);
        }
        while(curl > l){
            update(a[--curl], 1);
        }
        while(curr > r){
            update(a[curr--], -1);
        }
        while(curl < l){
            update(a[curl++], -1);
        }
        ans[qu[i].idx] += cnt;
    }
    for(i=0; i<q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message

tourism.cpp: In function 'void dfs(int)':
tourism.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0; i<graph[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
tourism.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5984 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 1 ms 5980 KB Output is correct
8 Correct 1 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 1 ms 5980 KB Output is correct
13 Correct 1 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 4 ms 6000 KB Output is correct
16 Correct 5 ms 5980 KB Output is correct
17 Correct 6 ms 5980 KB Output is correct
18 Correct 4 ms 5980 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 1 ms 5980 KB Output is correct
22 Correct 2 ms 5980 KB Output is correct
23 Correct 1 ms 5980 KB Output is correct
24 Correct 2 ms 5980 KB Output is correct
25 Correct 1 ms 5980 KB Output is correct
26 Correct 2 ms 5980 KB Output is correct
27 Correct 1 ms 5976 KB Output is correct
28 Correct 1 ms 5980 KB Output is correct
29 Correct 1 ms 6012 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5984 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 1 ms 5980 KB Output is correct
8 Correct 1 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 1 ms 5980 KB Output is correct
13 Correct 1 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 4 ms 6000 KB Output is correct
16 Correct 5 ms 5980 KB Output is correct
17 Correct 6 ms 5980 KB Output is correct
18 Correct 4 ms 5980 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 1 ms 5980 KB Output is correct
22 Correct 2 ms 5980 KB Output is correct
23 Correct 1 ms 5980 KB Output is correct
24 Correct 2 ms 5980 KB Output is correct
25 Correct 1 ms 5980 KB Output is correct
26 Correct 2 ms 5980 KB Output is correct
27 Correct 1 ms 5976 KB Output is correct
28 Correct 1 ms 5980 KB Output is correct
29 Correct 1 ms 6012 KB Output is correct
30 Correct 11 ms 5980 KB Output is correct
31 Correct 23 ms 5980 KB Output is correct
32 Correct 27 ms 5980 KB Output is correct
33 Correct 36 ms 5980 KB Output is correct
34 Correct 29 ms 5980 KB Output is correct
35 Correct 3 ms 5980 KB Output is correct
36 Correct 3 ms 5980 KB Output is correct
37 Correct 3 ms 5980 KB Output is correct
38 Correct 1521 ms 6204 KB Output is correct
39 Correct 1572 ms 6204 KB Output is correct
40 Correct 1742 ms 6236 KB Output is correct
41 Correct 28 ms 6232 KB Output is correct
42 Correct 30 ms 6240 KB Output is correct
43 Correct 18 ms 5980 KB Output is correct
44 Correct 867 ms 6176 KB Output is correct
45 Correct 423 ms 5980 KB Output is correct
46 Correct 1177 ms 6172 KB Output is correct
47 Correct 12 ms 5980 KB Output is correct
48 Correct 9 ms 6168 KB Output is correct
49 Correct 12 ms 5980 KB Output is correct
50 Correct 6 ms 6164 KB Output is correct
51 Correct 6 ms 5980 KB Output is correct
52 Correct 6 ms 5980 KB Output is correct
53 Correct 6 ms 5980 KB Output is correct
54 Correct 6 ms 6156 KB Output is correct
55 Correct 9 ms 5980 KB Output is correct
56 Correct 3 ms 5980 KB Output is correct
57 Correct 2 ms 6132 KB Output is correct
58 Correct 4 ms 5976 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5988 KB Output is correct
3 Correct 3 ms 6232 KB Output is correct
4 Execution timed out 5088 ms 12496 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 5976 KB Output is correct
2 Correct 29 ms 8524 KB Output is correct
3 Correct 38 ms 8652 KB Output is correct
4 Correct 36 ms 8948 KB Output is correct
5 Correct 46 ms 10228 KB Output is correct
6 Correct 58 ms 10580 KB Output is correct
7 Correct 60 ms 10324 KB Output is correct
8 Correct 53 ms 10400 KB Output is correct
9 Correct 55 ms 10320 KB Output is correct
10 Correct 56 ms 10344 KB Output is correct
11 Correct 52 ms 10340 KB Output is correct
12 Correct 62 ms 10496 KB Output is correct
13 Correct 62 ms 10820 KB Output is correct
14 Correct 76 ms 11012 KB Output is correct
15 Correct 85 ms 12484 KB Output is correct
16 Correct 61 ms 10932 KB Output is correct
17 Correct 64 ms 10940 KB Output is correct
18 Correct 57 ms 10772 KB Output is correct
19 Correct 1012 ms 10240 KB Output is correct
20 Correct 1293 ms 10372 KB Output is correct
21 Correct 1106 ms 10244 KB Output is correct
22 Correct 1345 ms 10400 KB Output is correct
23 Correct 1518 ms 10364 KB Output is correct
24 Correct 1370 ms 10324 KB Output is correct
25 Correct 1361 ms 10468 KB Output is correct
26 Correct 2072 ms 10424 KB Output is correct
27 Correct 1442 ms 10500 KB Output is correct
28 Correct 1145 ms 10324 KB Output is correct
29 Correct 1705 ms 10228 KB Output is correct
30 Correct 2200 ms 10584 KB Output is correct
31 Correct 1403 ms 11028 KB Output is correct
32 Correct 1606 ms 11032 KB Output is correct
33 Correct 1410 ms 11368 KB Output is correct
34 Correct 2738 ms 12548 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5976 KB Output is correct
2 Correct 1 ms 5984 KB Output is correct
3 Correct 3 ms 6020 KB Output is correct
4 Execution timed out 5069 ms 10448 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5984 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 1 ms 5980 KB Output is correct
8 Correct 1 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 1 ms 5980 KB Output is correct
13 Correct 1 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 4 ms 6000 KB Output is correct
16 Correct 5 ms 5980 KB Output is correct
17 Correct 6 ms 5980 KB Output is correct
18 Correct 4 ms 5980 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct
20 Correct 4 ms 5980 KB Output is correct
21 Correct 1 ms 5980 KB Output is correct
22 Correct 2 ms 5980 KB Output is correct
23 Correct 1 ms 5980 KB Output is correct
24 Correct 2 ms 5980 KB Output is correct
25 Correct 1 ms 5980 KB Output is correct
26 Correct 2 ms 5980 KB Output is correct
27 Correct 1 ms 5976 KB Output is correct
28 Correct 1 ms 5980 KB Output is correct
29 Correct 1 ms 6012 KB Output is correct
30 Correct 11 ms 5980 KB Output is correct
31 Correct 23 ms 5980 KB Output is correct
32 Correct 27 ms 5980 KB Output is correct
33 Correct 36 ms 5980 KB Output is correct
34 Correct 29 ms 5980 KB Output is correct
35 Correct 3 ms 5980 KB Output is correct
36 Correct 3 ms 5980 KB Output is correct
37 Correct 3 ms 5980 KB Output is correct
38 Correct 1521 ms 6204 KB Output is correct
39 Correct 1572 ms 6204 KB Output is correct
40 Correct 1742 ms 6236 KB Output is correct
41 Correct 28 ms 6232 KB Output is correct
42 Correct 30 ms 6240 KB Output is correct
43 Correct 18 ms 5980 KB Output is correct
44 Correct 867 ms 6176 KB Output is correct
45 Correct 423 ms 5980 KB Output is correct
46 Correct 1177 ms 6172 KB Output is correct
47 Correct 12 ms 5980 KB Output is correct
48 Correct 9 ms 6168 KB Output is correct
49 Correct 12 ms 5980 KB Output is correct
50 Correct 6 ms 6164 KB Output is correct
51 Correct 6 ms 5980 KB Output is correct
52 Correct 6 ms 5980 KB Output is correct
53 Correct 6 ms 5980 KB Output is correct
54 Correct 6 ms 6156 KB Output is correct
55 Correct 9 ms 5980 KB Output is correct
56 Correct 3 ms 5980 KB Output is correct
57 Correct 2 ms 6132 KB Output is correct
58 Correct 4 ms 5976 KB Output is correct
59 Correct 1 ms 5980 KB Output is correct
60 Correct 1 ms 5988 KB Output is correct
61 Correct 3 ms 6232 KB Output is correct
62 Execution timed out 5088 ms 12496 KB Time limit exceeded
63 Halted 0 ms 0 KB -