oj.uz

Submission #917260

# Submission time Handle Problem Language Result Execution time Memory
917260 2024-01-27T14:19:55 Z huutuan Tourism (JOI23_tourism) C++14
100 / 100
 3589 ms 51632 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=1e5+1, S=400, LG=18;

struct Query{
   int l, r, i;

   Query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}

   bool operator<(const Query& x){
      return l/S!=x.l/S?l<x.l:((l/S)&1?r<x.r:r>x.r);
   }
} qq[N];

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
   int lower_bound(int val){
      int ans=0;
      for (int i=16; i>=0; --i) if (ans+(1<<i)<=n && t[ans+(1<<i)]<val){
         ans+=1<<i;
         val-=t[ans];
      }
      return ans+1;
   }
};

int n, m, q, a[N], tdfs, tin[N], tout[N], dep[N], ans[N], cnt[N], tour[N];
int tin2[N], tout2[N], tdfs2;
pair<int, int> st[N*2][LG];
vector<int> g[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   tin2[u]=++tdfs2;
   tour[tdfs2]=u;
   dep[u]=dep[p]+1;
   st[tdfs][0]={dep[u], u};
   for (int v:g[u]) if (v!=p){
      dfs(v, u);
      ++tdfs;
      st[tdfs][0]={dep[u], u};
   }
   tout[u]=tdfs;
   tout2[u]=tdfs2;
}

void build(){
   for (int k=1; k<LG; ++k) for (int i=1; i+(1<<k)-1<=tdfs; ++i) st[i][k]=min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
}

int lca(int u, int v){
   u=tin[u]; v=tin[v];
   if (u>v) swap(u, v);
   int lg=__lg(v-u+1);
   return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

int distance(int u, int v){
   return dep[u]+dep[v]-dep[lca(u, v)]*2;
}

namespace among{
   struct SUS{
      int prev_arr[N], next_arr[N];
      int size;
      FenwickTree bit;
      int ans;
      int get_order(int x){
         return bit.get(x);
      }
      int find_by_order(int i){
         return bit.lower_bound(i);
      }
      int find_first(){
         return bit.lower_bound(1);
      }
      int find_last(){
         return bit.lower_bound(size);
      }
      void insert(int x){
         if (size){
            int i=get_order(x);
            int prev=i?find_by_order(i):find_last();
            int next=next_arr[prev];
            ans-=distance(tour[prev], tour[next]);
            ans+=distance(tour[prev], tour[x]);
            ans+=distance(tour[x], tour[next]);
            prev_arr[x]=prev; next_arr[prev]=x;
            prev_arr[next]=x; next_arr[x]=next;
         }
         bit.update(x, 1);
         if (!size){
            prev_arr[x]=x;
            next_arr[x]=x;
         }
         ++size;
      }
      void erase(int x){
         bit.update(x, -1);
         --size;
         if (size){
            int prev=prev_arr[x];
            int next=next_arr[x];
            ans+=distance(tour[prev], tour[next]);
            ans-=distance(tour[prev], tour[x]);
            ans-=distance(tour[x], tour[next]);
            prev_arr[next]=prev; next_arr[prev]=next;
         }
      }
   } us;
}

void solve(){
   #ifdef sus
   freopen("03-04.txt", "r", stdin);
   freopen("cf.out", "w", stdout);
   #endif
   cin >> n >> m >> q;
   for (int i=1; i<n; ++i){
      int x, y; cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
   dfs(1, 0);
   build();
   for (int i=1; i<=m; ++i) cin >> a[i];
   for (int i=1; i<=q; ++i){
      int x, y; cin >> x >> y;
      qq[i]={x, y, i};
   }
   sort(qq+1, qq+q+1);
   int cl=1, cr=0;
   among::us.bit.init(n*2);
   for (int i=1; i<=q; ++i){
      int l=qq[i].l, r=qq[i].r;
      while (l<cl){
         --cl;
         if (!cnt[tin2[a[cl]]]) among::us.insert(tin2[a[cl]]);
         ++cnt[tin2[a[cl]]];
      }
      while (r>cr){
         ++cr;
         if (!cnt[tin2[a[cr]]]) among::us.insert(tin2[a[cr]]);
         ++cnt[tin2[a[cr]]];
      }
      while (l>cl){
         --cnt[tin2[a[cl]]];
         if (!cnt[tin2[a[cl]]]) among::us.erase(tin2[a[cl]]);
         ++cl;
      }
      while (r<cr){
         --cnt[tin2[a[cr]]];
         if (!cnt[tin2[a[cr]]]) among::us.erase(tin2[a[cr]]);
         --cr;
      }
      ans[qq[i].i]=among::us.ans/2+1;
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7528 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7512 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7512 KB Output is correct
14 Correct 2 ms 7512 KB Output is correct
15 Correct 3 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 3 ms 7512 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7516 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7540 KB Output is correct
29 Correct 3 ms 7516 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7528 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7512 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7512 KB Output is correct
14 Correct 2 ms 7512 KB Output is correct
15 Correct 3 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 3 ms 7512 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7516 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7540 KB Output is correct
29 Correct 3 ms 7516 KB Output is correct
30 Correct 10 ms 7516 KB Output is correct
31 Correct 12 ms 7512 KB Output is correct
32 Correct 15 ms 7512 KB Output is correct
33 Correct 18 ms 7512 KB Output is correct
34 Correct 14 ms 7512 KB Output is correct
35 Correct 4 ms 7516 KB Output is correct
36 Correct 4 ms 7516 KB Output is correct
37 Correct 4 ms 7516 KB Output is correct
38 Correct 14 ms 7772 KB Output is correct
39 Correct 15 ms 7836 KB Output is correct
40 Correct 13 ms 7772 KB Output is correct
41 Correct 4 ms 7860 KB Output is correct
42 Correct 5 ms 7772 KB Output is correct
43 Correct 4 ms 7772 KB Output is correct
44 Correct 14 ms 7772 KB Output is correct
45 Correct 14 ms 7772 KB Output is correct
46 Correct 15 ms 7772 KB Output is correct
47 Correct 4 ms 7772 KB Output is correct
48 Correct 4 ms 7516 KB Output is correct
49 Correct 4 ms 7772 KB Output is correct
50 Correct 13 ms 7516 KB Output is correct
51 Correct 13 ms 7516 KB Output is correct
52 Correct 13 ms 7604 KB Output is correct
53 Correct 15 ms 7772 KB Output is correct
54 Correct 14 ms 7516 KB Output is correct
55 Correct 13 ms 7512 KB Output is correct
56 Correct 4 ms 7512 KB Output is correct
57 Correct 3 ms 7516 KB Output is correct
58 Correct 4 ms 7524 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 1618 ms 31904 KB Output is correct
5 Correct 1244 ms 41472 KB Output is correct
6 Correct 1779 ms 46928 KB Output is correct
7 Correct 2885 ms 48708 KB Output is correct
8 Correct 2742 ms 48712 KB Output is correct
9 Correct 2808 ms 48720 KB Output is correct
10 Correct 2785 ms 48704 KB Output is correct
11 Correct 2713 ms 48712 KB Output is correct
12 Correct 291 ms 51280 KB Output is correct
13 Correct 297 ms 51280 KB Output is correct
14 Correct 299 ms 51632 KB Output is correct
15 Correct 78 ms 49388 KB Output is correct
16 Correct 156 ms 51024 KB Output is correct
17 Correct 93 ms 9044 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 71 ms 25224 KB Output is correct
3 Correct 97 ms 27480 KB Output is correct
4 Correct 92 ms 29780 KB Output is correct
5 Correct 93 ms 40276 KB Output is correct
6 Correct 117 ms 40296 KB Output is correct
7 Correct 166 ms 40276 KB Output is correct
8 Correct 147 ms 40284 KB Output is correct
9 Correct 138 ms 40288 KB Output is correct
10 Correct 158 ms 40288 KB Output is correct
11 Correct 163 ms 40268 KB Output is correct
12 Correct 177 ms 40200 KB Output is correct
13 Correct 165 ms 40292 KB Output is correct
14 Correct 173 ms 40544 KB Output is correct
15 Correct 209 ms 40532 KB Output is correct
16 Correct 145 ms 40276 KB Output is correct
17 Correct 173 ms 40192 KB Output is correct
18 Correct 144 ms 40392 KB Output is correct
19 Correct 104 ms 40252 KB Output is correct
20 Correct 99 ms 40320 KB Output is correct
21 Correct 103 ms 40360 KB Output is correct
22 Correct 121 ms 40328 KB Output is correct
23 Correct 118 ms 40276 KB Output is correct
24 Correct 107 ms 40276 KB Output is correct
25 Correct 134 ms 40356 KB Output is correct
26 Correct 141 ms 40252 KB Output is correct
27 Correct 135 ms 40300 KB Output is correct
28 Correct 160 ms 40272 KB Output is correct
29 Correct 162 ms 40844 KB Output is correct
30 Correct 152 ms 40280 KB Output is correct
31 Correct 158 ms 40276 KB Output is correct
32 Correct 203 ms 40540 KB Output is correct
33 Correct 170 ms 40408 KB Output is correct
34 Correct 163 ms 40668 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 2086 ms 27868 KB Output is correct
5 Correct 2506 ms 27984 KB Output is correct
6 Correct 3190 ms 37656 KB Output is correct
7 Correct 3589 ms 43748 KB Output is correct
8 Correct 3480 ms 43752 KB Output is correct
9 Correct 3363 ms 43752 KB Output is correct
10 Correct 3584 ms 43760 KB Output is correct
11 Correct 3176 ms 43756 KB Output is correct
12 Correct 3425 ms 43880 KB Output is correct
13 Correct 3170 ms 43748 KB Output is correct
14 Correct 98 ms 9088 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7528 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7512 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7512 KB Output is correct
14 Correct 2 ms 7512 KB Output is correct
15 Correct 3 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 3 ms 7512 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7516 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7540 KB Output is correct
29 Correct 3 ms 7516 KB Output is correct
30 Correct 10 ms 7516 KB Output is correct
31 Correct 12 ms 7512 KB Output is correct
32 Correct 15 ms 7512 KB Output is correct
33 Correct 18 ms 7512 KB Output is correct
34 Correct 14 ms 7512 KB Output is correct
35 Correct 4 ms 7516 KB Output is correct
36 Correct 4 ms 7516 KB Output is correct
37 Correct 4 ms 7516 KB Output is correct
38 Correct 14 ms 7772 KB Output is correct
39 Correct 15 ms 7836 KB Output is correct
40 Correct 13 ms 7772 KB Output is correct
41 Correct 4 ms 7860 KB Output is correct
42 Correct 5 ms 7772 KB Output is correct
43 Correct 4 ms 7772 KB Output is correct
44 Correct 14 ms 7772 KB Output is correct
45 Correct 14 ms 7772 KB Output is correct
46 Correct 15 ms 7772 KB Output is correct
47 Correct 4 ms 7772 KB Output is correct
48 Correct 4 ms 7516 KB Output is correct
49 Correct 4 ms 7772 KB Output is correct
50 Correct 13 ms 7516 KB Output is correct
51 Correct 13 ms 7516 KB Output is correct
52 Correct 13 ms 7604 KB Output is correct
53 Correct 15 ms 7772 KB Output is correct
54 Correct 14 ms 7516 KB Output is correct
55 Correct 13 ms 7512 KB Output is correct
56 Correct 4 ms 7512 KB Output is correct
57 Correct 3 ms 7516 KB Output is correct
58 Correct 4 ms 7524 KB Output is correct
59 Correct 2 ms 7512 KB Output is correct
60 Correct 3 ms 7516 KB Output is correct
61 Correct 3 ms 7516 KB Output is correct
62 Correct 1618 ms 31904 KB Output is correct
63 Correct 1244 ms 41472 KB Output is correct
64 Correct 1779 ms 46928 KB Output is correct
65 Correct 2885 ms 48708 KB Output is correct
66 Correct 2742 ms 48712 KB Output is correct
67 Correct 2808 ms 48720 KB Output is correct
68 Correct 2785 ms 48704 KB Output is correct
69 Correct 2713 ms 48712 KB Output is correct
70 Correct 291 ms 51280 KB Output is correct
71 Correct 297 ms 51280 KB Output is correct
72 Correct 299 ms 51632 KB Output is correct
73 Correct 78 ms 49388 KB Output is correct
74 Correct 156 ms 51024 KB Output is correct
75 Correct 93 ms 9044 KB Output is correct
76 Correct 2 ms 7512 KB Output is correct
77 Correct 71 ms 25224 KB Output is correct
78 Correct 97 ms 27480 KB Output is correct
79 Correct 92 ms 29780 KB Output is correct
80 Correct 93 ms 40276 KB Output is correct
81 Correct 117 ms 40296 KB Output is correct
82 Correct 166 ms 40276 KB Output is correct
83 Correct 147 ms 40284 KB Output is correct
84 Correct 138 ms 40288 KB Output is correct
85 Correct 158 ms 40288 KB Output is correct
86 Correct 163 ms 40268 KB Output is correct
87 Correct 177 ms 40200 KB Output is correct
88 Correct 165 ms 40292 KB Output is correct
89 Correct 173 ms 40544 KB Output is correct
90 Correct 209 ms 40532 KB Output is correct
91 Correct 145 ms 40276 KB Output is correct
92 Correct 173 ms 40192 KB Output is correct
93 Correct 144 ms 40392 KB Output is correct
94 Correct 104 ms 40252 KB Output is correct
95 Correct 99 ms 40320 KB Output is correct
96 Correct 103 ms 40360 KB Output is correct
97 Correct 121 ms 40328 KB Output is correct
98 Correct 118 ms 40276 KB Output is correct
99 Correct 107 ms 40276 KB Output is correct
100 Correct 134 ms 40356 KB Output is correct
101 Correct 141 ms 40252 KB Output is correct
102 Correct 135 ms 40300 KB Output is correct
103 Correct 160 ms 40272 KB Output is correct
104 Correct 162 ms 40844 KB Output is correct
105 Correct 152 ms 40280 KB Output is correct
106 Correct 158 ms 40276 KB Output is correct
107 Correct 203 ms 40540 KB Output is correct
108 Correct 170 ms 40408 KB Output is correct
109 Correct 163 ms 40668 KB Output is correct
110 Correct 2 ms 7516 KB Output is correct
111 Correct 2 ms 7516 KB Output is correct
112 Correct 3 ms 7516 KB Output is correct
113 Correct 2086 ms 27868 KB Output is correct
114 Correct 2506 ms 27984 KB Output is correct
115 Correct 3190 ms 37656 KB Output is correct
116 Correct 3589 ms 43748 KB Output is correct
117 Correct 3480 ms 43752 KB Output is correct
118 Correct 3363 ms 43752 KB Output is correct
119 Correct 3584 ms 43760 KB Output is correct
120 Correct 3176 ms 43756 KB Output is correct
121 Correct 3425 ms 43880 KB Output is correct
122 Correct 3170 ms 43748 KB Output is correct
123 Correct 98 ms 9088 KB Output is correct
124 Correct 2919 ms 43924 KB Output is correct
125 Correct 1641 ms 42364 KB Output is correct
126 Correct 3480 ms 43868 KB Output is correct
127 Correct 3347 ms 43868 KB Output is correct
128 Correct 3491 ms 43872 KB Output is correct
129 Correct 3497 ms 44128 KB Output is correct
130 Correct 3362 ms 44116 KB Output is correct
131 Correct 2776 ms 50256 KB Output is correct
132 Correct 2877 ms 51480 KB Output is correct
133 Correct 2611 ms 47680 KB Output is correct
134 Correct 2825 ms 43956 KB Output is correct
135 Correct 3180 ms 43976 KB Output is correct
136 Correct 2964 ms 43912 KB Output is correct
137 Correct 3161 ms 44172 KB Output is correct
138 Correct 3299 ms 44404 KB Output is correct
139 Correct 3038 ms 44168 KB Output is correct
140 Correct 3137 ms 44232 KB Output is correct
141 Correct 3219 ms 44164 KB Output is correct
142 Correct 3101 ms 44180 KB Output is correct
143 Correct 86 ms 41560 KB Output is correct
144 Correct 202 ms 43720 KB Output is correct