제출 #370071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370071		Mamnoon_Siam	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	305 ms	22380 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

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 1e5 + 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) {
  debug(u);
  vis[u] = 1;
  onstk[u] = 1;
  while(true) {
    debug("ho");
    int flag = 0;
    {
      ii& r = ra[find(u)];
      debug(r);
      if(r.fi > 1) if(has(r.fi, r.se, C[r.fi-1])) {
        ++flag;
        if(!vis[r.fi-1]) {
          dfs(r.fi-1);
          // r = U(r, ra[find(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)];
      debug(r);
      if(r.se < n) if(has(r.fi, r.se, C[r.se])) {
        ++flag;
        if(!vis[r.se+1]) {
          dfs(r.se+1);
          // r = U(r, ra[find(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);
  }
  for(int i = 1; i <= n; ++i) {
    // debug(ra[find(i)]);
    // cout << ra[find(i)].fi << ' ' << ra[find(i)].se << endl;
  }

  // return 0;
  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;
}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In function 'void dfs(int)':
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:94:3: note: in expansion of macro 'debug'
   94 |   debug(u);
      |   ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:98:5: note: in expansion of macro 'debug'
   98 |     debug("ho");
      |     ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:102:7: note: in expansion of macro 'debug'
  102 |       debug(r);
      |       ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:119:7: note: in expansion of macro 'debug'
  119 |       debug(r);
      |       ^~~~~
long_mansion.cpp: In function 'int main(int, const char**)':
long_mansion.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |     scanf("%d", &C[i]);
      |     ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:153:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  153 |     int B; scanf("%d", &B);
      |            ~~~~~^~~~~~~~~~
long_mansion.cpp:155:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |       int x; scanf("%d", &x);
      |              ~~~~~^~~~~~~~~~
long_mansion.cpp:168:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  168 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  171 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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