oj.uz

Submission #536000

# Submission time Handle Problem Language Result Execution time Memory
536000 2022-03-12T05:02:06 Z cig32 Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 146584 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}

vector<int> adj[MAXN];

int l[MAXN], r[MAXN], c[MAXN];
vector<int> List[MAXN];
unordered_map<int, int> contains[MAXN];
bool vis[MAXN];
int n;

stack<int> topo;

void dfs(int node) {
  vis[node] = 1;
  for(int x: adj[node]) {
    if(!vis[x]) {
      dfs(x);
    }
  }
  topo.push(node);
}

vector<int> adj2[MAXN], adj3[MAXN];

vector<vector<int> > compo;
vector<int> single;

void dfs2(int node) {
  vis[node] = 1;
  for(int x: adj2[node]) {
    if(!vis[x]) dfs2(x);
  }
  single.push_back(node);
}

int dsu[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}

void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}

void dfs3(int node) {
  vis[node] = 1;
  topo.push(node); // reverse topo order
  for(int x: adj3[node]) {
    if(!vis[x]) {
      dfs3(x);
    }
  }
}

vector<int> savior[MAXN]; // savior[i]: which nodes contain key i

void solve(int tc) {
  cin >> n;
  for(int i=1; i<=n; i++) {
    dsu[i] = i;
  }
  for(int i=1; i<n; i++) {
    cin >> c[i];
  }
  for(int i=1; i<=n; i++) {
    int x;
    cin >> x;
    for(int j=0; j<x; j++) {
      int y;
      cin >> y;
      List[i].push_back(y);
      savior[y].push_back(i);
      contains[i][y] = 1;
    }
  }
  for(int i=1; i<n; i++) {
    if(contains[i][c[i]]) adj[i].push_back(i + 1);
    if(contains[i+1][c[i]]) adj[i + 1].push_back(i);
  }
  for(int i=1; i<=n; i++) {
    if(!vis[i]) {
      dfs(i);
    }
  }
  for(int i=1; i<=n; i++) {
    vis[i] = 0;
    for(int j=0; j<adj[i].size(); j++) {
      adj2[adj[i][j]].push_back(i);
    }
  }
  while(topo.size()) {
    int t = topo.top(); topo.pop();
    if(!vis[t]) {
      single.clear();
      dfs2(t);
      compo.push_back(single);
    }
  }
  for(vector<int> v: compo) {
    for(int i=1; i<v.size(); i++) {
      if(set_of(v[i]) != set_of(v[i-1])) union_(v[i], v[i-1]);
    }
  }
  map<pair<int, int>, int> exists;
  for(int i=1; i<=n; i++) {
    for(int x: adj[i]) {
      int si = set_of(i), sx = set_of(x);
      if(si != sx && !exists[{si, sx}]) {
        exists[{si, sx}] = exists[{sx, si}] = 1;
        adj3[si].push_back(sx);
      }
    }
  }
  for(int i=1; i<=n; i++) vis[i] = 0;
  for(int i=1; i<=n; i++) {
    if(set_of(i) == i && !vis[i]) {
      dfs3(i);
    }
  }
  for(int i=1; i<=n; i++) l[i] = r[i] = i;
  while(topo.size()) {
    int t = topo.top(); topo.pop();
    for(int x: adj3[t]) {
      l[t] = min(l[t], l[x]);
      r[t] = max(r[t], r[x]);
    }
    while(1) {
      bool can = 0;
      if(l[t] > 1) {
        int key_id = c[l[t] - 1];
        if(savior[key_id].size()) {
          if(savior[key_id][savior[key_id].size() - 1] >= l[t]) {
            int lwb = *lower_bound(savior[key_id].begin(), savior[key_id].end(), l[t]);
            if(lwb <= r[t]) {
              l[t]--;
              can = 1;
            }
          }
        }
      }
      if(r[t] < n) {
        int key_id = c[r[t]];
        if(savior[key_id].size()) {
          if(savior[key_id][savior[key_id].size() - 1] >= l[t]) {
            int lwb = *lower_bound(savior[key_id].begin(), savior[key_id].end(), l[t]);
            if(lwb <= r[t]) {
              r[t]++;
              can = 1;
            }
          }
        }
      }
      if(!can) break;
    }
  }
  for(int i=1; i<=n; i++) {
    l[i] = l[set_of(i)], r[i] = r[set_of(i)];
  }
  int q;
  cin >> q;
  while(q--) {
    int x, y; cin >> x >> y;
    cout << (l[x] <= y && y <= r[x] ? "YES\n" : "NO\n");
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

long_mansion.cpp: In function 'void solve(long long int)':
long_mansion.cpp:115:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int j=0; j<adj[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~~
long_mansion.cpp:128:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=1; i<v.size(); i++) {
      |                  ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 91216 KB Output is correct
2 Correct 118 ms 91676 KB Output is correct
3 Correct 313 ms 92408 KB Output is correct
4 Correct 58 ms 91016 KB Output is correct
5 Correct 55 ms 91180 KB Output is correct
6 Correct 54 ms 91080 KB Output is correct
7 Correct 57 ms 91020 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 91216 KB Output is correct
2 Correct 118 ms 91676 KB Output is correct
3 Correct 313 ms 92408 KB Output is correct
4 Correct 58 ms 91016 KB Output is correct
5 Correct 55 ms 91180 KB Output is correct
6 Correct 54 ms 91080 KB Output is correct
7 Correct 57 ms 91020 KB Output is correct
8 Correct 148 ms 92748 KB Output is correct
9 Correct 143 ms 92816 KB Output is correct
10 Correct 199 ms 94284 KB Output is correct
11 Correct 395 ms 98832 KB Output is correct
12 Correct 137 ms 96528 KB Output is correct
13 Correct 132 ms 97104 KB Output is correct
14 Correct 142 ms 97208 KB Output is correct
15 Correct 136 ms 97136 KB Output is correct
16 Correct 134 ms 96972 KB Output is correct
17 Correct 134 ms 97196 KB Output is correct
18 Correct 135 ms 97272 KB Output is correct
19 Correct 132 ms 97148 KB Output is correct
20 Correct 135 ms 97224 KB Output is correct
21 Correct 135 ms 96880 KB Output is correct
22 Correct 133 ms 97044 KB Output is correct
23 Correct 139 ms 97008 KB Output is correct
24 Correct 159 ms 96972 KB Output is correct
25 Correct 138 ms 96896 KB Output is correct
26 Correct 144 ms 96980 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 146584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 91216 KB Output is correct
2 Correct 118 ms 91676 KB Output is correct
3 Correct 313 ms 92408 KB Output is correct
4 Correct 58 ms 91016 KB Output is correct
5 Correct 55 ms 91180 KB Output is correct
6 Correct 54 ms 91080 KB Output is correct
7 Correct 57 ms 91020 KB Output is correct
8 Correct 148 ms 92748 KB Output is correct
9 Correct 143 ms 92816 KB Output is correct
10 Correct 199 ms 94284 KB Output is correct
11 Correct 395 ms 98832 KB Output is correct
12 Correct 137 ms 96528 KB Output is correct
13 Correct 132 ms 97104 KB Output is correct
14 Correct 142 ms 97208 KB Output is correct
15 Correct 136 ms 97136 KB Output is correct
16 Correct 134 ms 96972 KB Output is correct
17 Correct 134 ms 97196 KB Output is correct
18 Correct 135 ms 97272 KB Output is correct
19 Correct 132 ms 97148 KB Output is correct
20 Correct 135 ms 97224 KB Output is correct
21 Correct 135 ms 96880 KB Output is correct
22 Correct 133 ms 97044 KB Output is correct
23 Correct 139 ms 97008 KB Output is correct
24 Correct 159 ms 96972 KB Output is correct
25 Correct 138 ms 96896 KB Output is correct
26 Correct 144 ms 96980 KB Output is correct
27 Execution timed out 3070 ms 146584 KB Time limit exceeded
28 Halted 0 ms 0 KB -