# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
889724 |
2023-12-20T06:16:34 Z |
vjudge1 |
Tourism (JOI23_tourism) |
C++17 |
|
5000 ms |
61040 KB |
#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
tomorrow will worse
but the day after tomorrow will be the sunshine..
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const long long N = 2e5+50, inf = 1e18, mod = 1e9+7;
vi g[N];
set<pii> mp, jol;
set<int> chk;
void dfs(int pos, int pr){
if(chk.empty())return;
if(chk.count(pos) > 0){
chk.erase(chk.find(pos));
if(!jol.empty()){
for(auto i:jol){
mp.insert(i);
}
}
}
for(auto to:g[pos]){
if(to == pr)continue;
jol.insert({pos, to});
dfs(to, pos);
jol.erase(jol.find({pos, to}));
}
}
int st[17][N];
int st2[17][N];
int get(int l, int r) {
int cl = __lg(r - l + 1);
return min(st[cl][l], st[cl][r - (1 << cl) + 1]);
}
int getm(int l, int r) {
int cl = __lg(r - l + 1);
return max(st2[cl][l], st2[cl][r - (1 << cl) + 1]);
}
void solve(){
int n, m, q, a, b;
cin >> n >> m >> q;
bool ok = 1;
for(int i = 0; i < n-1; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
if(a!=i+1 || b!=i+2)ok = 0;
}
int pl[m+1]{};
for(int i = 1; i <= m; i++){
cin >> pl[i];
}
if(ok){
for(int i = 1; i <= m; i++){
st[0][i] = pl[i];
st2[0][i] = pl[i];
}
for (int i = 1; i <= __lg(n); i++) {
int len = 1 << (i - 1);
for (int j = 1; j <= n; j++) {
st[i][j] = min(st[i - 1][j], st[i - 1][ min(j + len, n) ]);
}
}
for (int i = 1; i <= __lg(n); i++) {
int len = 1 << (i - 1);
for (int j = 1; j <= n; j++) {
st2[i][j] = max(st2[i - 1][j], st2[i - 1][ min(j + len, n) ]);
}
}
while(q--){
int l, r;
cin >> l >> r;
cout << getm(l, r) - get(l, r)+1 << '\n';
}
}else{
while(q--){
int l, r;
cin >> l >> r;
for(int i = l+1; i <= r; i++)chk.insert(pl[i]);
dfs(pl[l], -1);
cout << mp.size()+1 << '\n';
mp.clear();
//~ queue<pii> q;
//~ q.push({pl[l], 0});
//~ int us[n+1]{};
//~ while(!q.empty()){
//~ auto [pos, ds] = q.front();
//~ cout << pos << ' ' << ds << '\n';
//~ q.pop();
//~ us[pos] = 1;
//~ for(auto to:g[pos]){
//~ if(us[to])continue;
//~ if(chk.count(to)){
//~ ans += ds+1;
//~ ds = 0;
//~ }
//~ }
//~ for(auto to:g[pos]){
//~ if(us[to])continue;
//~ if(chk.count(to)){
//~ chk.erase(to);
//~ q.push({to, 0});
//~ }else q.push({to, ds+1});
//~ }
//~ if(chk.empty())break;
//~ }
//~ cout << ans+1 << '\n';
}
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
//~ cin >> t;
while(t--){
solve();
}
}
Compilation message
tourism.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
124 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
4 ms |
21080 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
13 ms |
6748 KB |
Output is correct |
6 |
Correct |
10 ms |
6748 KB |
Output is correct |
7 |
Correct |
14 ms |
6956 KB |
Output is correct |
8 |
Correct |
12 ms |
6748 KB |
Output is correct |
9 |
Correct |
25 ms |
6940 KB |
Output is correct |
10 |
Correct |
25 ms |
6748 KB |
Output is correct |
11 |
Correct |
24 ms |
6748 KB |
Output is correct |
12 |
Correct |
43 ms |
6944 KB |
Output is correct |
13 |
Correct |
39 ms |
6744 KB |
Output is correct |
14 |
Correct |
39 ms |
6744 KB |
Output is correct |
15 |
Correct |
97 ms |
6744 KB |
Output is correct |
16 |
Correct |
93 ms |
7004 KB |
Output is correct |
17 |
Correct |
97 ms |
7004 KB |
Output is correct |
18 |
Correct |
68 ms |
6836 KB |
Output is correct |
19 |
Correct |
74 ms |
6968 KB |
Output is correct |
20 |
Correct |
83 ms |
6744 KB |
Output is correct |
21 |
Correct |
13 ms |
6748 KB |
Output is correct |
22 |
Correct |
13 ms |
6748 KB |
Output is correct |
23 |
Correct |
13 ms |
6748 KB |
Output is correct |
24 |
Correct |
13 ms |
6748 KB |
Output is correct |
25 |
Correct |
13 ms |
6748 KB |
Output is correct |
26 |
Correct |
13 ms |
6744 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
2 ms |
6940 KB |
Output is correct |
29 |
Correct |
1 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
4 ms |
21080 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
13 ms |
6748 KB |
Output is correct |
6 |
Correct |
10 ms |
6748 KB |
Output is correct |
7 |
Correct |
14 ms |
6956 KB |
Output is correct |
8 |
Correct |
12 ms |
6748 KB |
Output is correct |
9 |
Correct |
25 ms |
6940 KB |
Output is correct |
10 |
Correct |
25 ms |
6748 KB |
Output is correct |
11 |
Correct |
24 ms |
6748 KB |
Output is correct |
12 |
Correct |
43 ms |
6944 KB |
Output is correct |
13 |
Correct |
39 ms |
6744 KB |
Output is correct |
14 |
Correct |
39 ms |
6744 KB |
Output is correct |
15 |
Correct |
97 ms |
6744 KB |
Output is correct |
16 |
Correct |
93 ms |
7004 KB |
Output is correct |
17 |
Correct |
97 ms |
7004 KB |
Output is correct |
18 |
Correct |
68 ms |
6836 KB |
Output is correct |
19 |
Correct |
74 ms |
6968 KB |
Output is correct |
20 |
Correct |
83 ms |
6744 KB |
Output is correct |
21 |
Correct |
13 ms |
6748 KB |
Output is correct |
22 |
Correct |
13 ms |
6748 KB |
Output is correct |
23 |
Correct |
13 ms |
6748 KB |
Output is correct |
24 |
Correct |
13 ms |
6748 KB |
Output is correct |
25 |
Correct |
13 ms |
6748 KB |
Output is correct |
26 |
Correct |
13 ms |
6744 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
2 ms |
6940 KB |
Output is correct |
29 |
Correct |
1 ms |
6744 KB |
Output is correct |
30 |
Correct |
639 ms |
7004 KB |
Output is correct |
31 |
Correct |
827 ms |
7072 KB |
Output is correct |
32 |
Correct |
1336 ms |
7400 KB |
Output is correct |
33 |
Correct |
1352 ms |
7148 KB |
Output is correct |
34 |
Correct |
1299 ms |
7152 KB |
Output is correct |
35 |
Correct |
2451 ms |
7148 KB |
Output is correct |
36 |
Correct |
2496 ms |
7504 KB |
Output is correct |
37 |
Correct |
2546 ms |
7168 KB |
Output is correct |
38 |
Execution timed out |
5037 ms |
7656 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
21080 KB |
Output is correct |
2 |
Correct |
2 ms |
8796 KB |
Output is correct |
3 |
Correct |
2 ms |
9052 KB |
Output is correct |
4 |
Incorrect |
43 ms |
61040 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Execution timed out |
5083 ms |
9400 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
8796 KB |
Output is correct |
3 |
Correct |
2 ms |
9052 KB |
Output is correct |
4 |
Execution timed out |
5077 ms |
13128 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
4 ms |
21080 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
13 ms |
6748 KB |
Output is correct |
6 |
Correct |
10 ms |
6748 KB |
Output is correct |
7 |
Correct |
14 ms |
6956 KB |
Output is correct |
8 |
Correct |
12 ms |
6748 KB |
Output is correct |
9 |
Correct |
25 ms |
6940 KB |
Output is correct |
10 |
Correct |
25 ms |
6748 KB |
Output is correct |
11 |
Correct |
24 ms |
6748 KB |
Output is correct |
12 |
Correct |
43 ms |
6944 KB |
Output is correct |
13 |
Correct |
39 ms |
6744 KB |
Output is correct |
14 |
Correct |
39 ms |
6744 KB |
Output is correct |
15 |
Correct |
97 ms |
6744 KB |
Output is correct |
16 |
Correct |
93 ms |
7004 KB |
Output is correct |
17 |
Correct |
97 ms |
7004 KB |
Output is correct |
18 |
Correct |
68 ms |
6836 KB |
Output is correct |
19 |
Correct |
74 ms |
6968 KB |
Output is correct |
20 |
Correct |
83 ms |
6744 KB |
Output is correct |
21 |
Correct |
13 ms |
6748 KB |
Output is correct |
22 |
Correct |
13 ms |
6748 KB |
Output is correct |
23 |
Correct |
13 ms |
6748 KB |
Output is correct |
24 |
Correct |
13 ms |
6748 KB |
Output is correct |
25 |
Correct |
13 ms |
6748 KB |
Output is correct |
26 |
Correct |
13 ms |
6744 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
2 ms |
6940 KB |
Output is correct |
29 |
Correct |
1 ms |
6744 KB |
Output is correct |
30 |
Correct |
639 ms |
7004 KB |
Output is correct |
31 |
Correct |
827 ms |
7072 KB |
Output is correct |
32 |
Correct |
1336 ms |
7400 KB |
Output is correct |
33 |
Correct |
1352 ms |
7148 KB |
Output is correct |
34 |
Correct |
1299 ms |
7152 KB |
Output is correct |
35 |
Correct |
2451 ms |
7148 KB |
Output is correct |
36 |
Correct |
2496 ms |
7504 KB |
Output is correct |
37 |
Correct |
2546 ms |
7168 KB |
Output is correct |
38 |
Execution timed out |
5037 ms |
7656 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |