oj.uz

Submission #1087088

# Submission time Handle Problem Language Result Execution time Memory
1087088 2024-09-12T08:02:40 Z TraianDanciu Colors (RMI18_colors) C++17
100 / 100
 430 ms 73244 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26448 KB Output is correct
2 Correct 27 ms 25696 KB Output is correct
3 Correct 12 ms 25436 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 26452 KB Output is correct
2 Correct 28 ms 25680 KB Output is correct
3 Correct 13 ms 25180 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 26452 KB Output is correct
2 Correct 28 ms 25680 KB Output is correct
3 Correct 13 ms 25180 KB Output is correct
4 Correct 137 ms 28072 KB Output is correct
5 Correct 272 ms 44344 KB Output is correct
6 Correct 430 ms 62576 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26448 KB Output is correct
2 Correct 27 ms 25696 KB Output is correct
3 Correct 12 ms 25436 KB Output is correct
4 Correct 61 ms 26452 KB Output is correct
5 Correct 28 ms 25680 KB Output is correct
6 Correct 13 ms 25180 KB Output is correct
7 Correct 65 ms 26424 KB Output is correct
8 Correct 27 ms 25692 KB Output is correct
9 Correct 14 ms 25436 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 28256 KB Output is correct
2 Correct 254 ms 45124 KB Output is correct
3 Correct 279 ms 59960 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25936 KB Output is correct
2 Correct 18 ms 25688 KB Output is correct
3 Correct 13 ms 25328 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26448 KB Output is correct
2 Correct 27 ms 25696 KB Output is correct
3 Correct 12 ms 25436 KB Output is correct
4 Correct 67 ms 27120 KB Output is correct
5 Correct 61 ms 26452 KB Output is correct
6 Correct 28 ms 25680 KB Output is correct
7 Correct 13 ms 25180 KB Output is correct
8 Correct 137 ms 28072 KB Output is correct
9 Correct 272 ms 44344 KB Output is correct
10 Correct 430 ms 62576 KB Output is correct
11 Correct 65 ms 26424 KB Output is correct
12 Correct 27 ms 25692 KB Output is correct
13 Correct 14 ms 25436 KB Output is correct
14 Correct 108 ms 28256 KB Output is correct
15 Correct 254 ms 45124 KB Output is correct
16 Correct 279 ms 59960 KB Output is correct
17 Correct 32 ms 25936 KB Output is correct
18 Correct 18 ms 25688 KB Output is correct
19 Correct 13 ms 25328 KB Output is correct
20 Correct 82 ms 27516 KB Output is correct
21 Correct 282 ms 48108 KB Output is correct
22 Correct 418 ms 73244 KB Output is correct