Submission #370074

#	Time	Username	Problem	Language	Result	Execution time	Memory
370074		Mamnoon_Siam	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	620 ms	59100 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 5e5 + 5;

int n;
vi indices[N];
int par[N];
ii ra[N];
int C[N];

bool has(int l, int r, int x) {
  return upper_bound(all(indices[x]), r) != lower_bound(all(indices[x]), l);
}

ii U(ii x, ii y) { // assumption: intersects
  return {min(x.fi, y.fi), max(x.se, y.se)};
}

int find(int u) {
  assert(u);
  if(par[u] == u) return u;
  par[u] = find(par[u]);
  ra[par[u]] = U(ra[u], ra[par[u]]);
  return par[u];
}

void unite(int u, int v) {
  int pu = find(u), pv = find(v);
  if(pu != pv) {
    par[pu] = pv;
    find(pu);
  }
}

int onstk[N], vis[N];

void dfs(int u) {
  vis[u] = 1;
  onstk[u] = 1;
  while(true) {
    int flag = 0;
    {
      ii& r = ra[find(u)];
      if(r.fi > 1) if(has(r.fi, r.se, C[r.fi-1])) {
        ++flag;
        if(!vis[r.fi-1]) {
          dfs(r.fi-1);
        } else {
          if(onstk[r.fi-1]) {
            unite(u, r.fi-1);
          } else {
            r = U(r, ra[find(r.fi-1)]);
          }
        }
      }
    }
    {
      ii& r = ra[find(u)];
      if(r.se < n) if(has(r.fi, r.se, C[r.se])) {
        ++flag;
        if(!vis[r.se+1]) {
          dfs(r.se+1);
        } else {
          if(onstk[r.se+1]) {
            unite(u, r.se+1);
          } else {
            r = U(r, ra[find(r.se+1)]);
          }
        }
      }
    }
    if(!flag) {
      break;
    }
  }
  onstk[u] = 0;
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  for(int i = 1; i < n; ++i) {
    scanf("%d", &C[i]);
  }
  for(int i = 1; i <= n; ++i) {
    ra[i] = {i, i};
    par[i] = i;
    int B; scanf("%d", &B);
    while(B--) {
      int x; scanf("%d", &x);
      indices[x].emplace_back(i);
    }
  }
  for(int i = 1; i <= n; ++i) {
    if(!vis[i]) dfs(i);
  }
  int q; scanf("%d", &q);
  while(q--) {
    int x, y;
    scanf("%d %d", &x, &y);
    puts(ra[find(x)].fi <= y and y <= ra[find(x)].se ? "YES" : "NO");
  }
  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main(int, const char**)':
long_mansion.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |     scanf("%d", &C[i]);
      |     ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:101:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |     int B; scanf("%d", &B);
      |            ~~~~~^~~~~~~~~~
long_mansion.cpp:103:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |       int x; scanf("%d", &x);
      |              ~~~~~^~~~~~~~~~
long_mansion.cpp:110:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75