# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
793678 | 2023-07-26T05:28:57 Z | vjudge1 | Tourism (JOI23_tourism) | C++17 | 157 ms | 12948 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 = 2e5 + 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 < 20; i++) for (int j = 1; j + (1 << i) <= (m + 1); 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 if(s == 0){ while(q--){ cin>>l>>r; mn = 1e9, mx = 0; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 6612 KB | Output is correct |
2 | Correct | 3 ms | 6484 KB | Output is correct |
3 | Correct | 3 ms | 6484 KB | Output is correct |
4 | Correct | 4 ms | 6612 KB | Output is correct |
5 | Correct | 4 ms | 6612 KB | Output is correct |
6 | Correct | 4 ms | 6612 KB | Output is correct |
7 | Correct | 4 ms | 6612 KB | Output is correct |
8 | Correct | 4 ms | 6612 KB | Output is correct |
9 | Correct | 5 ms | 6544 KB | Output is correct |
10 | Correct | 5 ms | 6612 KB | Output is correct |
11 | Correct | 5 ms | 6612 KB | Output is correct |
12 | Correct | 4 ms | 6612 KB | Output is correct |
13 | Correct | 6 ms | 6612 KB | Output is correct |
14 | Correct | 5 ms | 6612 KB | Output is correct |
15 | Correct | 5 ms | 6612 KB | Output is correct |
16 | Correct | 5 ms | 6612 KB | Output is correct |
17 | Correct | 5 ms | 6612 KB | Output is correct |
18 | Correct | 5 ms | 6612 KB | Output is correct |
19 | Correct | 5 ms | 6612 KB | Output is correct |
20 | Correct | 5 ms | 6612 KB | Output is correct |
21 | Correct | 6 ms | 6612 KB | Output is correct |
22 | Correct | 5 ms | 6552 KB | Output is correct |
23 | Correct | 5 ms | 6612 KB | Output is correct |
24 | Correct | 5 ms | 6612 KB | Output is correct |
25 | Correct | 5 ms | 6612 KB | Output is correct |
26 | Correct | 5 ms | 6612 KB | Output is correct |
27 | Correct | 4 ms | 6484 KB | Output is correct |
28 | Correct | 4 ms | 6612 KB | Output is correct |
29 | Correct | 4 ms | 6612 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 6612 KB | Output is correct |
2 | Correct | 3 ms | 6484 KB | Output is correct |
3 | Correct | 3 ms | 6484 KB | Output is correct |
4 | Correct | 4 ms | 6612 KB | Output is correct |
5 | Correct | 4 ms | 6612 KB | Output is correct |
6 | Correct | 4 ms | 6612 KB | Output is correct |
7 | Correct | 4 ms | 6612 KB | Output is correct |
8 | Correct | 4 ms | 6612 KB | Output is correct |
9 | Correct | 5 ms | 6544 KB | Output is correct |
10 | Correct | 5 ms | 6612 KB | Output is correct |
11 | Correct | 5 ms | 6612 KB | Output is correct |
12 | Correct | 4 ms | 6612 KB | Output is correct |
13 | Correct | 6 ms | 6612 KB | Output is correct |
14 | Correct | 5 ms | 6612 KB | Output is correct |
15 | Correct | 5 ms | 6612 KB | Output is correct |
16 | Correct | 5 ms | 6612 KB | Output is correct |
17 | Correct | 5 ms | 6612 KB | Output is correct |
18 | Correct | 5 ms | 6612 KB | Output is correct |
19 | Correct | 5 ms | 6612 KB | Output is correct |
20 | Correct | 5 ms | 6612 KB | Output is correct |
21 | Correct | 6 ms | 6612 KB | Output is correct |
22 | Correct | 5 ms | 6552 KB | Output is correct |
23 | Correct | 5 ms | 6612 KB | Output is correct |
24 | Correct | 5 ms | 6612 KB | Output is correct |
25 | Correct | 5 ms | 6612 KB | Output is correct |
26 | Correct | 5 ms | 6612 KB | Output is correct |
27 | Correct | 4 ms | 6484 KB | Output is correct |
28 | Correct | 4 ms | 6612 KB | Output is correct |
29 | Correct | 4 ms | 6612 KB | Output is correct |
30 | Correct | 48 ms | 6720 KB | Output is correct |
31 | Correct | 56 ms | 6720 KB | Output is correct |
32 | Correct | 108 ms | 6768 KB | Output is correct |
33 | Correct | 88 ms | 6776 KB | Output is correct |
34 | Correct | 89 ms | 6784 KB | Output is correct |
35 | Correct | 57 ms | 6784 KB | Output is correct |
36 | Correct | 59 ms | 6740 KB | Output is correct |
37 | Correct | 66 ms | 6780 KB | Output is correct |
38 | Correct | 69 ms | 6740 KB | Output is correct |
39 | Correct | 64 ms | 6872 KB | Output is correct |
40 | Correct | 67 ms | 6868 KB | Output is correct |
41 | Correct | 70 ms | 6896 KB | Output is correct |
42 | Correct | 72 ms | 6896 KB | Output is correct |
43 | Correct | 66 ms | 6740 KB | Output is correct |
44 | Correct | 70 ms | 6820 KB | Output is correct |
45 | Correct | 65 ms | 6740 KB | Output is correct |
46 | Correct | 67 ms | 6820 KB | Output is correct |
47 | Correct | 69 ms | 6804 KB | Output is correct |
48 | Correct | 64 ms | 6740 KB | Output is correct |
49 | Correct | 66 ms | 6740 KB | Output is correct |
50 | Correct | 67 ms | 6824 KB | Output is correct |
51 | Correct | 66 ms | 6740 KB | Output is correct |
52 | Correct | 66 ms | 6740 KB | Output is correct |
53 | Correct | 65 ms | 6740 KB | Output is correct |
54 | Correct | 69 ms | 6740 KB | Output is correct |
55 | Correct | 67 ms | 6780 KB | Output is correct |
56 | Correct | 8 ms | 6612 KB | Output is correct |
57 | Correct | 49 ms | 6612 KB | Output is correct |
58 | Correct | 48 ms | 6740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 6504 KB | Output is correct |
2 | Correct | 3 ms | 6484 KB | Output is correct |
3 | Correct | 7 ms | 6612 KB | Output is correct |
4 | Incorrect | 157 ms | 12948 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 6484 KB | Output is correct |
2 | Incorrect | 40 ms | 10004 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 6484 KB | Output is correct |
2 | Correct | 3 ms | 6484 KB | Output is correct |
3 | Correct | 8 ms | 6612 KB | Output is correct |
4 | Incorrect | 61 ms | 10736 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 6612 KB | Output is correct |
2 | Correct | 3 ms | 6484 KB | Output is correct |
3 | Correct | 3 ms | 6484 KB | Output is correct |
4 | Correct | 4 ms | 6612 KB | Output is correct |
5 | Correct | 4 ms | 6612 KB | Output is correct |
6 | Correct | 4 ms | 6612 KB | Output is correct |
7 | Correct | 4 ms | 6612 KB | Output is correct |
8 | Correct | 4 ms | 6612 KB | Output is correct |
9 | Correct | 5 ms | 6544 KB | Output is correct |
10 | Correct | 5 ms | 6612 KB | Output is correct |
11 | Correct | 5 ms | 6612 KB | Output is correct |
12 | Correct | 4 ms | 6612 KB | Output is correct |
13 | Correct | 6 ms | 6612 KB | Output is correct |
14 | Correct | 5 ms | 6612 KB | Output is correct |
15 | Correct | 5 ms | 6612 KB | Output is correct |
16 | Correct | 5 ms | 6612 KB | Output is correct |
17 | Correct | 5 ms | 6612 KB | Output is correct |
18 | Correct | 5 ms | 6612 KB | Output is correct |
19 | Correct | 5 ms | 6612 KB | Output is correct |
20 | Correct | 5 ms | 6612 KB | Output is correct |
21 | Correct | 6 ms | 6612 KB | Output is correct |
22 | Correct | 5 ms | 6552 KB | Output is correct |
23 | Correct | 5 ms | 6612 KB | Output is correct |
24 | Correct | 5 ms | 6612 KB | Output is correct |
25 | Correct | 5 ms | 6612 KB | Output is correct |
26 | Correct | 5 ms | 6612 KB | Output is correct |
27 | Correct | 4 ms | 6484 KB | Output is correct |
28 | Correct | 4 ms | 6612 KB | Output is correct |
29 | Correct | 4 ms | 6612 KB | Output is correct |
30 | Correct | 48 ms | 6720 KB | Output is correct |
31 | Correct | 56 ms | 6720 KB | Output is correct |
32 | Correct | 108 ms | 6768 KB | Output is correct |
33 | Correct | 88 ms | 6776 KB | Output is correct |
34 | Correct | 89 ms | 6784 KB | Output is correct |
35 | Correct | 57 ms | 6784 KB | Output is correct |
36 | Correct | 59 ms | 6740 KB | Output is correct |
37 | Correct | 66 ms | 6780 KB | Output is correct |
38 | Correct | 69 ms | 6740 KB | Output is correct |
39 | Correct | 64 ms | 6872 KB | Output is correct |
40 | Correct | 67 ms | 6868 KB | Output is correct |
41 | Correct | 70 ms | 6896 KB | Output is correct |
42 | Correct | 72 ms | 6896 KB | Output is correct |
43 | Correct | 66 ms | 6740 KB | Output is correct |
44 | Correct | 70 ms | 6820 KB | Output is correct |
45 | Correct | 65 ms | 6740 KB | Output is correct |
46 | Correct | 67 ms | 6820 KB | Output is correct |
47 | Correct | 69 ms | 6804 KB | Output is correct |
48 | Correct | 64 ms | 6740 KB | Output is correct |
49 | Correct | 66 ms | 6740 KB | Output is correct |
50 | Correct | 67 ms | 6824 KB | Output is correct |
51 | Correct | 66 ms | 6740 KB | Output is correct |
52 | Correct | 66 ms | 6740 KB | Output is correct |
53 | Correct | 65 ms | 6740 KB | Output is correct |
54 | Correct | 69 ms | 6740 KB | Output is correct |
55 | Correct | 67 ms | 6780 KB | Output is correct |
56 | Correct | 8 ms | 6612 KB | Output is correct |
57 | Correct | 49 ms | 6612 KB | Output is correct |
58 | Correct | 48 ms | 6740 KB | Output is correct |
59 | Correct | 4 ms | 6504 KB | Output is correct |
60 | Correct | 3 ms | 6484 KB | Output is correct |
61 | Correct | 7 ms | 6612 KB | Output is correct |
62 | Incorrect | 157 ms | 12948 KB | Output isn't correct |
63 | Halted | 0 ms | 0 KB | - |