oj.uz

Submission #645257

# Submission time Handle Problem Language Result Execution time Memory
645257 2022-09-26T14:27:40 Z Alex_tz307 Colors (RMI18_colors) C++17
100 / 100
 435 ms 119024 KB 
#include <bits/stdc++.h>

using namespace std;

/// Observatia 1: Daca a[u] < b[u] => Nu am solutie pentru ca a poate doar sa scada, nu sa creasca.
/// La fel si pe parcurs, nu pot sa-l fac pe a[u] < b[u], pentru ca nu voi mai obtine solutie.

/// Observatia 2: Daca vreau sa fac o culoare c sa ajunga la u trebuie sa urmeze un drum astfel
/// incat pentru orice nod v din acel drum c <= a[v] si b[v] <= c(din observatia anterioara).

/// Observatia 3: Pentru ca un nod u sa fie rezolvat trebuie sa existe un nod v astfel incat
/// a[v] = b[u] si un drum de la u la v astfel incat pentru orice nod w de pe acel drum:
/// a[v] <= a[w] si b[w] <= a[v](reiese din observatiile anterioare).

/// Pornind de la aceste observatii se obtine o solutie bruta simpla: Pentru fiecare culoare c ce
/// apare in input construim un graf doar cu nodurile care satisfac proprietatea de la observatia 3
/// pentru c(c <= a[v] si b[v] <= c), iar apoi pentru toate nodurile cu b[v] = c verificam daca
/// exista un nod in componenta lor conexa astfel incat a[nod] = c.

/// Pot identifica fiecare muchie (u, v) prin 2 parametrii l si r: l = max(b[u], b[v]), r = min(a[u], a[v]).
/// => c <= r si l <= c <=> l <= c <= r. Astfel, se ajunge la un set de muchii active pentru anumite
/// intervale de timp si query-uri in privinta unor componente conexe, ceea ce se poate rezolva evident
/// cu dyanmic connectivity(offline pentru ca se stiu intervalele muchiilor de la inceput).

/// Cand am un query la momentul de timp c verific pentru toate nodurile cu b[nod] = c daca exista
/// in componenta lor un nod v astfel incat a[v] = c. Pentru asta pot marca toate componentele ce
/// contin un nod v astfel incat a[v] = c ca fiind corespunzatoare, iar apoi sa le demarchez.
/// Complexitatea amortizata a acestui pas va fi liniara, iar toata solutia va avea complexitatea
/// O(M * log^2(N)) de la dynamic connectivity(M muchii, O(log) intervale de split la intervalul
/// unei muchii si O(log) complexitatea unei operatii in DSU fara path compression).

const int kN = 1e5 + 5e4;
int a[1 + kN], b[1 + kN];
vector<int> A[1 + kN], B[1 + kN];

struct edge_t {
  int l, r, u, v;
};

struct DSU {
  vector<int> p, r, stk;
  vector<bool> mark;

  void init(int n) {
    p.resize(n + 1);
    iota(p.begin(), p.end(), 0);
    r.assign(n + 1, 1);
    mark.resize(n + 1);
  }

  int root(int x) {
    while (x != p[x]) {
      x = p[x];
    }
    return x;
  }

  void unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return;
    }
    if (r[y] < r[x]) {
      swap(x, y);
    }
    p[x] = y;
    r[y] += r[x];
    stk.emplace_back(x);
  }

  int currTime() {
    return stk.size();
  }

  void rollback(int checkpoint) {
    while ((int)stk.size() > checkpoint) {
      int x = stk.back();
      stk.pop_back();
      r[p[x]] -= r[x];
      p[x] = x;
    }
  }

  void update(int x, bool v) {
    mark[root(x)] = v;
  }

  bool check(int x) {
    return mark[root(x)];
  }
} dsu;

bool segIntersect(int a, int b, int c, int d) {
  return max(a, c) <= min(b, d);
}

bool solve(int l, int r, const vector<edge_t> &edges) {
  if (r < l) {
    return true;
  }
  int mid = (l + r) / 2;
  vector<edge_t> left, right;
  int checkpoint = dsu.currTime();
  for (const auto &it : edges) {
    if (it.l <= l && r <= it.r) {
      dsu.unite(it.u, it.v);
    } else {
      if (segIntersect(l, mid, it.l, it.r)) {
        left.emplace_back(it);
      }
      if (segIntersect(mid + 1, r, it.l, it.r)) {
        right.emplace_back(it);
      }
    }
  }
  if (l == r) {
    for (const int &v : A[l]) {
      dsu.update(v, true);
    }
    bool res = true;
    for (const int &v : B[l]) {
      res &= dsu.check(v);
      if (res == false) {
        break;
      }
    }
    for (const int &v : A[l]) {
      dsu.update(v, false);
    }
    dsu.rollback(checkpoint);
    return res;
  }
  bool res = solve(l, mid, left);
  if (res) {
    res = solve(mid + 1, r, right);
  }
  left.clear();
  right.clear();
  dsu.rollback(checkpoint);
  return res;
}

void testCase() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    A[i].clear();
    B[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    A[a[i]].emplace_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
    B[b[i]].emplace_back(i);
  }
  vector<edge_t> edges(m);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    edges[i] = {max(b[u], b[v]), min(a[u], a[v]), u, v};
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i] < b[i]) {
      cout << "0\n";
      return;
    }
  }
  dsu.init(n);
  if (solve(1, n, edges)) {
    cout << "1\n";
  } else {
    cout << "0\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8812 KB Output is correct
2 Correct 25 ms 7936 KB Output is correct
3 Correct 6 ms 7892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9232 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8784 KB Output is correct
2 Correct 29 ms 7920 KB Output is correct
3 Correct 6 ms 7636 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8784 KB Output is correct
2 Correct 29 ms 7920 KB Output is correct
3 Correct 6 ms 7636 KB Output is correct
4 Correct 139 ms 10512 KB Output is correct
5 Correct 330 ms 28360 KB Output is correct
6 Correct 435 ms 49748 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8812 KB Output is correct
2 Correct 25 ms 7936 KB Output is correct
3 Correct 6 ms 7892 KB Output is correct
4 Correct 77 ms 8784 KB Output is correct
5 Correct 29 ms 7920 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 66 ms 8808 KB Output is correct
8 Correct 26 ms 7956 KB Output is correct
9 Correct 8 ms 7892 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10492 KB Output is correct
2 Correct 274 ms 30132 KB Output is correct
3 Correct 254 ms 34456 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8288 KB Output is correct
2 Correct 16 ms 8344 KB Output is correct
3 Correct 8 ms 7696 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8812 KB Output is correct
2 Correct 25 ms 7936 KB Output is correct
3 Correct 6 ms 7892 KB Output is correct
4 Correct 67 ms 9232 KB Output is correct
5 Correct 77 ms 8784 KB Output is correct
6 Correct 29 ms 7920 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 139 ms 10512 KB Output is correct
9 Correct 330 ms 28360 KB Output is correct
10 Correct 435 ms 49748 KB Output is correct
11 Correct 66 ms 8808 KB Output is correct
12 Correct 26 ms 7956 KB Output is correct
13 Correct 8 ms 7892 KB Output is correct
14 Correct 135 ms 10492 KB Output is correct
15 Correct 274 ms 30132 KB Output is correct
16 Correct 254 ms 34456 KB Output is correct
17 Correct 31 ms 8288 KB Output is correct
18 Correct 16 ms 8344 KB Output is correct
19 Correct 8 ms 7696 KB Output is correct
20 Correct 93 ms 10184 KB Output is correct
21 Correct 305 ms 36312 KB Output is correct
22 Correct 406 ms 119024 KB Output is correct