# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
789187 |
2023-07-21T07:14:29 Z |
반딧불(#10041) |
Tourism (JOI23_tourism) |
C++17 |
|
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);
| ~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |