Submission #1117288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117288		ntdaccode	Tourism (JOI23_tourism)	C++17	35 / 100	5061 ms	31164 KiB

tourism

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=1e3+10;
const int mod=1e9+7;

int n,m,q,c[M];
vector<int> ke[M];

namespace sub {
   int num[M],tail[M],cnt = 0, up[M][20], d[M];
   void dfs(int u,int p)
   {
      num[u] = ++cnt;
      for(int i =1;i <= 18; i++) up[u][i] = up[up[u][i-1]][i-1];
      for(int v : ke[u]) {
         if(v == p) continue;
         up[v][0] = u;
         d[v] = d[u] + 1;
         dfs(v,u);
      }
      tail[u] = cnt;
   }

   bool anc(int u,int v)
   {
      return num[u] <= num[v] && tail[u] >= tail[v];
   }

   int lca(int u,int v)
   {
      if(anc(u,v)) return u;
      if(anc(v,u)) return v;
      for(int i = 18;i >=0 ; i--) if(!anc(up[u][i],v)) u = up[u][i];
      return up[u][0];
   }

   int dist(int u,int v)
   {
      int x = lca(u,v);
      return d[u] + d[v] - 2 * d[x];
   }

   bool cmp(const int &a,const int &b)
   {
      return num[a] < num[b];
   }
   void solve()
   {
      up[1][0] = 1;
     dfs(1,0);
     while(q--) {
        int l,r;
         cin >> l >> r;
        // cout << l << " " << r << "\n";

         vector<int> Q;
         for(int i = l;i <= r; i++) Q.pb(c[i]);

         sort(Q.begin(),Q.end(),cmp);
         int sz = Q.size();
         for(int i = 0;i <= sz - 2; i++) {
            Q.pb(lca(Q[i],Q[i + 1]));
         }
         //for(int v : Q) cout << v << " ";
         sort(Q.begin(),Q.end(),cmp);
         Q.resize(unique(Q.begin(),Q.end()) - Q.begin());
         stack<int> sk;
         int kq = 0;
         for(int v : Q) {
            while(!sk.empty() && !anc(sk.top(),v)) sk.pop();
            if(!sk.empty()) kq += dist(sk.top(),v);
            sk.push(v);
         }
         cout << kq  + 1 << "\n";

     }
   }
}

namespace sub3
{
   vector<tp> Q;
   vector<int> pos[M];
   int ma[M],mi[M];

   void dnc(int l,int r,vector<tp> &cur) {
      if(l > r) return ;
      int mid = (l + r)/2;
      vector<tp> L;
      vector<tp> R;
      int u,v,idx;

      fori(i,0,cur.size() - 1) {
            tie(u,v,idx) = cur[i];
            if(v < mid) {
               L.pb({u,v,idx});
               continue;
            }
            if(u > mid) {
               R.pb({u,v,idx});
               continue;
            }
            pos[u].pb(idx);
            pos[v].pb(idx);
      }
      cur.clear();
      int mx = 0,mn = 1e9;
      for(int i = mid;i >= l; i--) {
         mx = max(mx,c[i]);
         mn = min(mn,c[i]);
         for(int idx : pos[i]) {
            ma[idx] = max(ma[idx],mx);
            mi[idx] = min(mi[idx],mn);
         }
      }
      mx = 0,mn = 1e9;
      for(int i = mid;i <= r; i++) {
         mx = max(mx,c[i]);
         mn = min(mn,c[i]);
         for(int idx : pos[i]) {
            ma[idx] = max(ma[idx],mx);
            mi[idx] = min(mi[idx],mn);
         }
      }
      for(int i = l;i <= r; i++) pos[i].clear();

      if(L.size()) dnc(l, mid - 1, L);
      if(R.size()) dnc(mid + 1 , r, R);
   }

   void solve()
   {
      for(int i = 1; i <= q; i++) {
         int l,r;
         cin >> l >> r;
         Q.pb({l,r,i});
      }
      for(int i =1; i <= q; i++) mi[i] = 1e9;
      dnc(1,m,Q);
      for(int i = 1;i <= q; i++) {
            cout << ma[i]  - mi[i] + 1 << "\n";

      }
   }
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task "tourism"
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n >> m >> q;
  int ok = 0;
  for(int i = 1;i <= n - 1; i++) {
      int u,v;
      cin >> u >> v;
      ke[u].pb(v);
      ke[v].pb(u);
      if(u != i || v != i + 1) ok = 1;
  }
  for(int i = 1;i <= m; i++) cin >> c[i];
  if(ok == 1) sub :: solve();
  else sub3 :: solve();

}

Compilation message (stderr)

tourism.cpp: In function 'void sub3::dnc(long long int, long long int, std::vector<std::tuple<long long int, long long int, long long int> >&)':
tourism.cpp:2:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define fori(i,a,b) for(int i=a;i<=b;i++)
......
  100 |       fori(i,0,cur.size() - 1) {
      |            ~~~~~~~~~~~~~~~~~~     
tourism.cpp:100:7: note: in expansion of macro 'fori'
  100 |       fori(i,0,cur.size() - 1) {
      |       ^~~~
tourism.cpp: In function 'int32_t main()':
tourism.cpp:161:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
tourism.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
tourism.cpp:167:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:168:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41