# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
793699 | 2023-07-26T05:38:36 Z | vjudge1 | Tourism (JOI23_tourism) | C++17 | 100 ms | 15304 KB |
// Author : حسن #include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define fi first #define se second #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 3e5 + 9 , mod = 1e9 + 7; ll c[N] = {} , d[N] = {} , a[N] = {}, b[N] = {} , us[N] , us1[N] , st[N][20][2] , dp[N] = {}; vector<int>v[N]; void dfs(int n,int p = 0){ d[n] = d[p] + 1; for(auto to : v[n]) if(to != p) dfs(to , n); } ll ans; void dfs1(int n,int p = 0){ for(auto to : v[n]) if(to != p) dfs1(to , n); ll s = 0; for(auto to : v[n]) if(b[to] != 0) if(to != p) s++, b[n] = b[to]; if(s != 0){ if(s == 1 && us[n] == 0){ }else { ans++; for(auto to : v[n]) if(to != p && b[to] != 0){ ans += d[b[to]] - d[n] - 1; } b[n] = n; } }else if(us[n] == 1){ ans++; b[n] = n; } } pair<ll,ll> get(int x , int y){ ll i = dp[y - x + 1]; ll minimum = min(st[i][x][1], st[i][y - (1 << i) + 1][1]); ll maximum = max(st[i][x][0], st[i][y - (1 << i) + 1][0]); //cout<<i<<" "<<minimum<<" "<<maximum<<" "; return {maximum , minimum}; } void get1(){ ll x ,y , i; x = 0; y = 1; dp[0] = 0; for(i = 1; i <= 2e5; i++){ if(2 * y <= i) x++, y *= 2; dp[i] = x; } } void solve(){ ll q , i , j , m , n , z , s = 0, f, l , r , k , x , y , mn = 1e18 , mx = 0; cin>>n>>m>>q; for(i = 1; i < n; i++){ cin>>l>>r; v[l].pb(r); v[r].pb(l); if(!(l == i && r == i + 1)) s++; } for(i = 1; i <= m; i++) cin>>a[i]; dfs(1); get1(); for(i = 1; i <= m; i++) st[0][i][0] = st[0][i][1] = d[a[i]]; for (int i = 1; i < 18; i++) for (int j = 1; j + (1 << i) <= (m + 2); j++){ st[i][j][0] = max(st[i - 1][j][0], st[i - 1][j + (1 << (i - 1))][0]); st[i][j][1] = min(st[i - 1][j][1], st[i - 1][j + (1 << (i - 1))][1]); } if(s && n <= 2000 && m <= 2000 && q <= 2000){ while(q--){ cin>>l>>r; for(i = 1; i <= n; i++){ us[i] = b[i] = c[i] = 0; } for(i = l; i <= r; i++) us[a[i]] = 1; ans = 0; dfs1(1); cout<<ans<<"\n"; } }else { while(q--){ cin>>l>>r; cout<<get(l , r).fi - get(l , r).se + 1<<"\n"; } } } int main(){ TL; /* #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif */ int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8916 KB | Output is correct |
2 | Correct | 4 ms | 8916 KB | Output is correct |
3 | Correct | 4 ms | 8916 KB | Output is correct |
4 | Correct | 4 ms | 8916 KB | Output is correct |
5 | Correct | 5 ms | 8916 KB | Output is correct |
6 | Correct | 4 ms | 8916 KB | Output is correct |
7 | Correct | 4 ms | 8916 KB | Output is correct |
8 | Correct | 5 ms | 8916 KB | Output is correct |
9 | Correct | 5 ms | 8916 KB | Output is correct |
10 | Correct | 5 ms | 8916 KB | Output is correct |
11 | Correct | 6 ms | 8924 KB | Output is correct |
12 | Correct | 6 ms | 8916 KB | Output is correct |
13 | Correct | 5 ms | 8988 KB | Output is correct |
14 | Correct | 5 ms | 8916 KB | Output is correct |
15 | Correct | 5 ms | 9008 KB | Output is correct |
16 | Correct | 5 ms | 9000 KB | Output is correct |
17 | Correct | 5 ms | 8916 KB | Output is correct |
18 | Correct | 5 ms | 8916 KB | Output is correct |
19 | Correct | 5 ms | 8916 KB | Output is correct |
20 | Correct | 5 ms | 8928 KB | Output is correct |
21 | Correct | 7 ms | 8916 KB | Output is correct |
22 | Correct | 5 ms | 8916 KB | Output is correct |
23 | Correct | 5 ms | 8916 KB | Output is correct |
24 | Correct | 5 ms | 8916 KB | Output is correct |
25 | Correct | 5 ms | 8980 KB | Output is correct |
26 | Correct | 5 ms | 8916 KB | Output is correct |
27 | Correct | 4 ms | 8916 KB | Output is correct |
28 | Correct | 5 ms | 8916 KB | Output is correct |
29 | Correct | 5 ms | 8916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8916 KB | Output is correct |
2 | Correct | 4 ms | 8916 KB | Output is correct |
3 | Correct | 4 ms | 8916 KB | Output is correct |
4 | Correct | 4 ms | 8916 KB | Output is correct |
5 | Correct | 5 ms | 8916 KB | Output is correct |
6 | Correct | 4 ms | 8916 KB | Output is correct |
7 | Correct | 4 ms | 8916 KB | Output is correct |
8 | Correct | 5 ms | 8916 KB | Output is correct |
9 | Correct | 5 ms | 8916 KB | Output is correct |
10 | Correct | 5 ms | 8916 KB | Output is correct |
11 | Correct | 6 ms | 8924 KB | Output is correct |
12 | Correct | 6 ms | 8916 KB | Output is correct |
13 | Correct | 5 ms | 8988 KB | Output is correct |
14 | Correct | 5 ms | 8916 KB | Output is correct |
15 | Correct | 5 ms | 9008 KB | Output is correct |
16 | Correct | 5 ms | 9000 KB | Output is correct |
17 | Correct | 5 ms | 8916 KB | Output is correct |
18 | Correct | 5 ms | 8916 KB | Output is correct |
19 | Correct | 5 ms | 8916 KB | Output is correct |
20 | Correct | 5 ms | 8928 KB | Output is correct |
21 | Correct | 7 ms | 8916 KB | Output is correct |
22 | Correct | 5 ms | 8916 KB | Output is correct |
23 | Correct | 5 ms | 8916 KB | Output is correct |
24 | Correct | 5 ms | 8916 KB | Output is correct |
25 | Correct | 5 ms | 8980 KB | Output is correct |
26 | Correct | 5 ms | 8916 KB | Output is correct |
27 | Correct | 4 ms | 8916 KB | Output is correct |
28 | Correct | 5 ms | 8916 KB | Output is correct |
29 | Correct | 5 ms | 8916 KB | Output is correct |
30 | Correct | 43 ms | 9120 KB | Output is correct |
31 | Correct | 54 ms | 9112 KB | Output is correct |
32 | Correct | 87 ms | 9156 KB | Output is correct |
33 | Correct | 100 ms | 9144 KB | Output is correct |
34 | Correct | 85 ms | 9044 KB | Output is correct |
35 | Correct | 55 ms | 9156 KB | Output is correct |
36 | Correct | 54 ms | 9044 KB | Output is correct |
37 | Correct | 56 ms | 9160 KB | Output is correct |
38 | Correct | 64 ms | 9244 KB | Output is correct |
39 | Correct | 62 ms | 9172 KB | Output is correct |
40 | Correct | 65 ms | 9252 KB | Output is correct |
41 | Correct | 67 ms | 9268 KB | Output is correct |
42 | Correct | 70 ms | 9252 KB | Output is correct |
43 | Correct | 65 ms | 9176 KB | Output is correct |
44 | Correct | 63 ms | 9188 KB | Output is correct |
45 | Correct | 64 ms | 9180 KB | Output is correct |
46 | Correct | 65 ms | 9204 KB | Output is correct |
47 | Correct | 64 ms | 9172 KB | Output is correct |
48 | Correct | 77 ms | 9176 KB | Output is correct |
49 | Correct | 62 ms | 9196 KB | Output is correct |
50 | Correct | 60 ms | 9164 KB | Output is correct |
51 | Correct | 67 ms | 9168 KB | Output is correct |
52 | Correct | 62 ms | 9168 KB | Output is correct |
53 | Correct | 62 ms | 9164 KB | Output is correct |
54 | Correct | 62 ms | 9172 KB | Output is correct |
55 | Correct | 62 ms | 9044 KB | Output is correct |
56 | Correct | 5 ms | 8916 KB | Output is correct |
57 | Correct | 46 ms | 9100 KB | Output is correct |
58 | Correct | 44 ms | 9160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8916 KB | Output is correct |
2 | Correct | 5 ms | 8848 KB | Output is correct |
3 | Correct | 4 ms | 8968 KB | Output is correct |
4 | Incorrect | 41 ms | 15304 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8916 KB | Output is correct |
2 | Incorrect | 22 ms | 12332 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8916 KB | Output is correct |
2 | Correct | 4 ms | 8916 KB | Output is correct |
3 | Correct | 4 ms | 8916 KB | Output is correct |
4 | Incorrect | 41 ms | 13344 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8916 KB | Output is correct |
2 | Correct | 4 ms | 8916 KB | Output is correct |
3 | Correct | 4 ms | 8916 KB | Output is correct |
4 | Correct | 4 ms | 8916 KB | Output is correct |
5 | Correct | 5 ms | 8916 KB | Output is correct |
6 | Correct | 4 ms | 8916 KB | Output is correct |
7 | Correct | 4 ms | 8916 KB | Output is correct |
8 | Correct | 5 ms | 8916 KB | Output is correct |
9 | Correct | 5 ms | 8916 KB | Output is correct |
10 | Correct | 5 ms | 8916 KB | Output is correct |
11 | Correct | 6 ms | 8924 KB | Output is correct |
12 | Correct | 6 ms | 8916 KB | Output is correct |
13 | Correct | 5 ms | 8988 KB | Output is correct |
14 | Correct | 5 ms | 8916 KB | Output is correct |
15 | Correct | 5 ms | 9008 KB | Output is correct |
16 | Correct | 5 ms | 9000 KB | Output is correct |
17 | Correct | 5 ms | 8916 KB | Output is correct |
18 | Correct | 5 ms | 8916 KB | Output is correct |
19 | Correct | 5 ms | 8916 KB | Output is correct |
20 | Correct | 5 ms | 8928 KB | Output is correct |
21 | Correct | 7 ms | 8916 KB | Output is correct |
22 | Correct | 5 ms | 8916 KB | Output is correct |
23 | Correct | 5 ms | 8916 KB | Output is correct |
24 | Correct | 5 ms | 8916 KB | Output is correct |
25 | Correct | 5 ms | 8980 KB | Output is correct |
26 | Correct | 5 ms | 8916 KB | Output is correct |
27 | Correct | 4 ms | 8916 KB | Output is correct |
28 | Correct | 5 ms | 8916 KB | Output is correct |
29 | Correct | 5 ms | 8916 KB | Output is correct |
30 | Correct | 43 ms | 9120 KB | Output is correct |
31 | Correct | 54 ms | 9112 KB | Output is correct |
32 | Correct | 87 ms | 9156 KB | Output is correct |
33 | Correct | 100 ms | 9144 KB | Output is correct |
34 | Correct | 85 ms | 9044 KB | Output is correct |
35 | Correct | 55 ms | 9156 KB | Output is correct |
36 | Correct | 54 ms | 9044 KB | Output is correct |
37 | Correct | 56 ms | 9160 KB | Output is correct |
38 | Correct | 64 ms | 9244 KB | Output is correct |
39 | Correct | 62 ms | 9172 KB | Output is correct |
40 | Correct | 65 ms | 9252 KB | Output is correct |
41 | Correct | 67 ms | 9268 KB | Output is correct |
42 | Correct | 70 ms | 9252 KB | Output is correct |
43 | Correct | 65 ms | 9176 KB | Output is correct |
44 | Correct | 63 ms | 9188 KB | Output is correct |
45 | Correct | 64 ms | 9180 KB | Output is correct |
46 | Correct | 65 ms | 9204 KB | Output is correct |
47 | Correct | 64 ms | 9172 KB | Output is correct |
48 | Correct | 77 ms | 9176 KB | Output is correct |
49 | Correct | 62 ms | 9196 KB | Output is correct |
50 | Correct | 60 ms | 9164 KB | Output is correct |
51 | Correct | 67 ms | 9168 KB | Output is correct |
52 | Correct | 62 ms | 9168 KB | Output is correct |
53 | Correct | 62 ms | 9164 KB | Output is correct |
54 | Correct | 62 ms | 9172 KB | Output is correct |
55 | Correct | 62 ms | 9044 KB | Output is correct |
56 | Correct | 5 ms | 8916 KB | Output is correct |
57 | Correct | 46 ms | 9100 KB | Output is correct |
58 | Correct | 44 ms | 9160 KB | Output is correct |
59 | Correct | 4 ms | 8916 KB | Output is correct |
60 | Correct | 5 ms | 8848 KB | Output is correct |
61 | Correct | 4 ms | 8968 KB | Output is correct |
62 | Incorrect | 41 ms | 15304 KB | Output isn't correct |
63 | Halted | 0 ms | 0 KB | - |