Submission #1087088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087088		TraianDanciu	Colors (RMI18_colors)	C++17	100 / 100	430 ms	73244 KiB

colors

#include <stdio.h>
#include <vector>
#include <set>

static inline int min(int a, int b) {
  return a < b ? a : b;
}
static inline int max(int a, int b) {
  return a > b ? a : b;
}

#define MAXN 150000
#define MAXM 200000

char rez[MAXN + 1];
int u[MAXM], v[MAXM], have[MAXN], want[MAXN], n;
std::vector<int> g[MAXN], have_list[MAXN], want_list[MAXN];
std::set<int> sefi;

struct DSU {
  int sef[MAXN], card[MAXN], sp;
  struct JoinOP {
    int i, j, icard, jcard;
  } stiva[MAXN];

  void start() {
    int i;
    sp = 0;
    for(i = 0; i < n; i++) {
      sef[i] = i;
      card[i] = 1;
    }
  }

  int find(int i) {
    if(i == sef[i]) {
      return i;
    }
    return find(sef[i]);
  }

  void join(int i, int j) {
    if((i = find(i)) != (j = find(j))) {
      if(card[i] < card[j]) {
        std::swap(i, j);
      }

      stiva[sp++] = (struct JoinOP){.i = i, .j = j,
                    .icard = card[i], .jcard = card[j]};
      sef[j] = i;
      card[i] += card[j];
    }
  }

  void rollback(int where) {
    while(sp > where) {
      sp--;
      sef[stiva[sp].j] = stiva[sp].j;
      card[stiva[sp].i] = stiva[sp].icard;
      card[stiva[sp].j] = stiva[sp].jcard;
    }
  }
} dsu;

struct SegmentTree {
  std::vector<int> aint[4 * MAXN];
  int qleft, qright, qval;

  void start() {
    int i;
    for(i = 0; i < 4 * n; i++) {
      aint[i].clear();
    }
  }

  void _update(int node, int left, int right) {
    int middle;
    if(qleft <= left && right <= qright) {
      aint[node].push_back(qval);
    } else {
      middle = (left + right) / 2;
      if(qleft <= middle) {
        _update(2 * node + 1, left, middle);
      }
      if(middle < qright) {
        _update(2 * node + 2, middle + 1, right);
      }
    }
  }
  void update(int qleft, int qright, int qval) {
    this->qleft = qleft;
    this->qright = qright;
    this->qval = qval;
    _update(0, 0, n - 1);
  }

  void _query(int node, int left, int right) {
    int middle, i, sp;
    sp = dsu.sp;
    for(i = 0; i < (int)aint[node].size(); i++) {
      dsu.join(u[aint[node][i]], v[aint[node][i]]);
    }
      
    if(left == right) {
      for(i = 0; i < (int)have_list[left].size(); i++) {
        sefi.insert(dsu.find(have_list[left][i]));
      }
      for(i = 0; i < (int)want_list[left].size(); i++) {
        if(sefi.count(dsu.find(want_list[left][i]))) {
          rez[want_list[left][i]] = 1;
        }
      }
      sefi.clear();
    } else {
      middle = (left + right) / 2;
      _query(2 * node + 1, left, middle);
      _query(2 * node + 2, middle + 1, right);
    }

    dsu.rollback(sp);
  }
  void query() {
    dsu.start();
    _query(0, 0, n - 1);
  }
} aint;

int main() {
  int t, m, i, st, dr;

  scanf("%d", &t);
  while(t--) {
    scanf("%d%d", &n, &m);

    for(i = 0; i < n; i++) {
      scanf("%d", &have[i]);
      have_list[--have[i]].push_back(i);
    }
    for(i = 0; i < n; i++) {
      scanf("%d", &want[i]);
      want_list[--want[i]].push_back(i);
    }
    for(i = 0; i < m; i++) {
      scanf("%d%d", &u[i], &v[i]);
      g[--u[i]].push_back(--v[i]);
      g[v[i]].push_back(u[i]);
    }

    aint.start();
    for(i = 0; i < m; i++) {
      st = max(want[u[i]], want[v[i]]);
      dr = min(have[u[i]], have[v[i]]);
      if(st <= dr) {
        aint.update(st, dr, i);
      }
    }

    aint.query();
    i = rez[n] = 0; // rez[n] e santinela
    while(rez[i]) {
      i++;
    }
    printf("%d\n", i == n);

    for(i = 0; i < n; i++) {
      rez[i] = 0;
      g[i].clear();
      have_list[i].clear();
      want_list[i].clear();
    }
  }

  return 0;
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
colors.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:136:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |       scanf("%d", &have[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:140:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |       scanf("%d", &want[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:144:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |       scanf("%d%d", &u[i], &v[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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