oj.uz

Submission #370066

# Submission time Handle Problem Language Result Execution time Memory
370066 2021-02-23T07:22:26 Z Mamnoon_Siam Long Mansion (JOI17_long_mansion) C++17
0 / 100
 277 ms 17388 KB 
#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) {
  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)]);
  }
  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

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:93:3: note: in expansion of macro 'debug'
   93 |   debug(u);
      |   ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:97:5: note: in expansion of macro 'debug'
   97 |     debug("ho");
      |     ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:101:7: note: in expansion of macro 'debug'
  101 |       debug(r);
      |       ^~~~~
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:118:7: note: in expansion of macro 'debug'
  118 |       debug(r);
      |       ^~~~~
long_mansion.cpp: In function 'int main(int, const char**)':
long_mansion.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:162:5: note: in expansion of macro 'debug'
  162 |     debug(ra[find(i)]);
      |     ^~~~~
long_mansion.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  145 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  147 |     scanf("%d", &C[i]);
      |     ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:152:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |     int B; scanf("%d", &B);
      |            ~~~~~^~~~~~~~~~
long_mansion.cpp:154:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |       int x; scanf("%d", &x);
      |              ~~~~~^~~~~~~~~~
long_mansion.cpp:164:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 17388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2924 KB Output isn't correct
2 Halted 0 ms 0 KB -