Submission #1117276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117276		ntdaccode	Tourism (JOI23_tourism)	C++17	28 / 100	5077 ms	51088 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=1e6+10;
const int N=1e3+10;
const int mod=1e9+7;

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

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];
}

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;
  for(int i = 1;i <= n - 1; i++) {
      int u,v;
      cin >> u >> v;
      ke[u].pb(v);
      ke[v].pb(u);
  }
  up[1][0] = 1;
  dfs(1,0);
  for(int i = 1;i <= m; i++) cin >> c[i];
  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";

  }

}

Compilation message (stderr)

tourism.cpp: In function 'int32_t main()':
tourism.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
tourism.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
tourism.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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