oj.uz

Submission #370071

# Submission time Handle Problem Language Result Execution time Memory
370071 2021-02-23T07:39:22 Z Mamnoon_Siam Long Mansion (JOI17_long_mansion) C++17
25 / 100
 305 ms 22380 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) {
  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;
}

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: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2796 KB Output is correct
2 Correct 7 ms 2924 KB Output is correct
3 Correct 9 ms 3052 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2796 KB Output is correct
2 Correct 7 ms 2924 KB Output is correct
3 Correct 9 ms 3052 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct
8 Correct 134 ms 4460 KB Output is correct
9 Correct 149 ms 4460 KB Output is correct
10 Correct 138 ms 4608 KB Output is correct
11 Correct 141 ms 4844 KB Output is correct
12 Correct 132 ms 4588 KB Output is correct
13 Correct 140 ms 4588 KB Output is correct
14 Correct 136 ms 4532 KB Output is correct
15 Correct 131 ms 4716 KB Output is correct
16 Correct 128 ms 4972 KB Output is correct
17 Correct 138 ms 4660 KB Output is correct
18 Correct 134 ms 4588 KB Output is correct
19 Correct 163 ms 4588 KB Output is correct
20 Correct 130 ms 4864 KB Output is correct
21 Correct 129 ms 4972 KB Output is correct
22 Correct 132 ms 4588 KB Output is correct
23 Correct 137 ms 4460 KB Output is correct
24 Correct 133 ms 4460 KB Output is correct
25 Correct 135 ms 4480 KB Output is correct
26 Correct 135 ms 4332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 9836 KB Output is correct
2 Correct 304 ms 14488 KB Output is correct
3 Correct 296 ms 19156 KB Output is correct
4 Correct 295 ms 17132 KB Output is correct
5 Correct 302 ms 17260 KB Output is correct
6 Correct 261 ms 18028 KB Output is correct
7 Correct 231 ms 21612 KB Output is correct
8 Correct 223 ms 21868 KB Output is correct
9 Correct 227 ms 21868 KB Output is correct
10 Correct 232 ms 22124 KB Output is correct
11 Correct 232 ms 22380 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2796 KB Output is correct
2 Correct 7 ms 2924 KB Output is correct
3 Correct 9 ms 3052 KB Output is correct
4 Correct 5 ms 2796 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct
8 Correct 134 ms 4460 KB Output is correct
9 Correct 149 ms 4460 KB Output is correct
10 Correct 138 ms 4608 KB Output is correct
11 Correct 141 ms 4844 KB Output is correct
12 Correct 132 ms 4588 KB Output is correct
13 Correct 140 ms 4588 KB Output is correct
14 Correct 136 ms 4532 KB Output is correct
15 Correct 131 ms 4716 KB Output is correct
16 Correct 128 ms 4972 KB Output is correct
17 Correct 138 ms 4660 KB Output is correct
18 Correct 134 ms 4588 KB Output is correct
19 Correct 163 ms 4588 KB Output is correct
20 Correct 130 ms 4864 KB Output is correct
21 Correct 129 ms 4972 KB Output is correct
22 Correct 132 ms 4588 KB Output is correct
23 Correct 137 ms 4460 KB Output is correct
24 Correct 133 ms 4460 KB Output is correct
25 Correct 135 ms 4480 KB Output is correct
26 Correct 135 ms 4332 KB Output is correct
27 Correct 305 ms 9836 KB Output is correct
28 Correct 304 ms 14488 KB Output is correct
29 Correct 296 ms 19156 KB Output is correct
30 Correct 295 ms 17132 KB Output is correct
31 Correct 302 ms 17260 KB Output is correct
32 Correct 261 ms 18028 KB Output is correct
33 Correct 231 ms 21612 KB Output is correct
34 Correct 223 ms 21868 KB Output is correct
35 Correct 227 ms 21868 KB Output is correct
36 Correct 232 ms 22124 KB Output is correct
37 Correct 232 ms 22380 KB Output is correct
38 Runtime error 113 ms 13292 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -