oj.uz

Submission #789187

# Submission time Handle Problem Language Result Execution time Memory
789187 2023-07-21T07:14:29 Z 반딧불(#10041) Tourism (JOI23_tourism) C++17
0 / 100
 2 ms 2724 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k, q;
vector<int> link[100002];

int inCnt, in[100002], out[100002];
int par[100002], LCADB[100002][20], depth[100002];
int arr[100002];

void dfs(int x, int p=-1){
    in[x] = ++inCnt;
    for(auto y: link[x]){
        if(y==p) continue;
        par[y] = x, depth[y] = depth[x] + 1;
        dfs(y, x);
    }
    out[x] = inCnt;
}

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=19; d>=0; d--) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int getDist(int x, int y){
    return depth[x] + depth[y] - depth[getLCA(x, y)] * 2;
}

struct segTree{
    int treeMin[400002], treeMax[400002];
    void init(int i, int l, int r, int *arr){
        if(l==r){
            treeMin[i] = treeMax[i] = arr[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        treeMin[i] = min(treeMin[i*2], treeMin[i*2+1]);
        treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);
    }
    int queryMin(int i, int l, int r, int s, int e){
        if(r<s||e<l) return INT_MAX;
        if(s<=l&&r<=e) return treeMin[i];
        int m = (l+r)>>1;
        return min(queryMin(i*2, l, m, s, e), queryMin(i*2+1, m+1, r, s, e));
    }
    int queryMax(int i, int l, int r, int s, int e){
        if(r<s||e<l) return INT_MIN;
        if(s<=l&&r<=e) return treeMax[i];
        int m = (l+r)>>1;
        return max(queryMax(i*2, l, m, s, e), queryMax(i*2+1, m+1, r, s, e));
    }
} tree;

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }
    dfs(1);
    for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
    tree.init(1, 1, n, arr);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", tree.queryMax(1, 1, n, l, r) - tree.queryMin(1, 1, n, l, r) + 1);
    }
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:75:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
tourism.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -