Submission #1203708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203708		lopkus	Colors (RMI18_colors)	C++20	47 / 100	3091 ms	6652 KiB

colors

#include <bits/stdc++.h>

#define int int64_t

const int inf = 1e18;

const int N = 5001;

struct Dsu{
    std::vector<int> P, siz;
    void make(int n) {
      P.resize(n + 1);
      siz.resize(n + 1);
    }
    void add(int v){
        P[v]=v;
        siz[v]=1;
        return;
    }
    int parent(int x){
        if(x==P[x])return x;
        return P[x]=parent(P[x]);
    }
    void add(int u,int v){
        u=parent(u);
        v=parent(v);
        if(u!=v){
            if(siz[u]<siz[v])std::swap(u,v);
            P[v]=u;
            siz[u]+=siz[v];
        }
        return;
    }
    int same(int u, int v) {
        return parent(u) == parent(v);
    }
};

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> b(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> b[i];
  }
  std::vector<std::array<int, 2>> edges(m + 1);
  for(int i = 1; i <= m; i++) {
    std::cin >> edges[i][0] >> edges[i][1];
  }
  int ok = 1;
  for(int i = 1; i <= n; i++) {
    ok &= (a[i] >= b[i]);
  }
  if(!ok) {
    std::cout << 0 << "\n";
    return;
  }
  std::vector<std::array<int, 2>> pq;
  for(int i = 1; i <= n; i++) {
    pq.push_back({b[i], i});
  }
  sort(pq.begin(), pq.end());
  reverse(pq.begin(), pq.end());
  std::set<int> st[n + 1];
  for(int i = 1; i <= n; i++) {
    st[a[i]].insert(i);
  }
  for(int ix = 0; ix < n; ix++) {
    int i = pq[ix][1];
    if(a[i] == b[i]) {
      continue;
    }
    Dsu dsu;
    dsu.make(n + 1);
    for(int e = 1; e <= n; e++) {
      dsu.add(e);
    }
    for(int e = 1; e <= m; e++) {
      int u = edges[e][0];
      int v = edges[e][1];
      if(b[i] >= std::max(b[u], b[v]) && b[i] <= std::min(a[u], a[v])) {
        dsu.add(u, v);
      }
    }
    int can = 0;
    for(auto posible : st[b[i]]) {
      can |= dsu.same(i, posible);
    }
    ok &= can;
    if(!ok) {
      break;
    }
    st[a[i]].erase(i);
    st[b[i]].insert(i);
  }
  std::cout << ok << "\n";
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 0 / 15
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 10 / 10
• Subtask 8: 0 / 22