Submission #645257

#	Time	Username	Problem	Language	Result	Execution time	Memory
645257		Alex_tz307	Colors (RMI18_colors)	C++17	100 / 100	435 ms	119024 KiB

colors

#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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22