Submission #646239

#	Time	Username	Problem	Language	Result	Execution time	Memory
646239		Matteo_Verz	Colors (RMI18_colors)	C++17	100 / 100	615 ms	87576 KiB

colors

/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '
 
using namespace std;
 
const int INF = 2e9;
const int N = 150000;
const int M = 250000;
 
struct Edge {
  int from, to;
};
 
Edge ve[1 + M];
int a[1 + N], b[1 + N];
vector <int> cola[1 + N], colb[1 + N];
 
class DSU {
  private:
    struct DSUedge {
      int node;
      int from, to;
      int size_from, size_to;
 
      DSUedge() {
        node = from = to = size_from = size_to = 0;
      }
 
      DSUedge(int nod, int x, int y, int szx, int szy) {
        node = nod;
        from = x; to = y;
        size_from = szx; size_to = szy;
      }
    };
 
    vector <int> rank;
    vector <int> parent;
    vector <bool> goodComponent;
    stack <DSUedge> st;
    
    public:
      void Init(int n) {
        while(st.size()) st.pop();
        rank.resize(1 + n);
        parent.resize(1 + n);
        goodComponent.resize(1 + n);
        
        for(int i = 1; i <= n; i++) {
          rank[i] = 1;
          parent[i] = i;
          goodComponent[i] = false;
        }
      }
 
      int Find(int x) {
        if(parent[x] == x) return x;
        return Find(parent[x]);
      }
 
      void Unite(int node, int x, int y) {
        x = Find(x);
        y = Find(y);
 
        if(x == y) return;
        
        if(rank[x] < rank[y]) swap(x, y);
        DSUedge e = {node, x, y, rank[x], rank[y]};
        
        st.push(e);
        parent[y] = x;
        rank[x] += rank[y];
        rank[y] = rank[x];
      }
 
      void RollBack(int node) {
        while(st.size() && st.top().node == node) {
          DSUedge e = st.top();
          st.pop();
 
          rank[e.from] = e.size_from; rank[e.to] = e.size_to;
          parent[e.from] = e.from; parent[e.to] = e.to;
        }
      }
 
      void ChangeValue(int node, bool value) {
        node = Find(node);
        goodComponent[node] = value;
      }
 
      bool IsGood(int node) {
        node = Find(node);
        return goodComponent[node];
      }
};
 
class Segment_Tree {
  private:
    vector <vector <Edge>> ev;
    DSU dsu;
 
  public:
    void Init(int n, int m) {
      ev.resize(1 + 4 * n);
      for(int i = 0; i < ev.size(); i++)
        ev[i].clear();
      dsu.Init(n);
    }
 
    void Update(int node, int l, int r, int x, int y, Edge e) {
      if(x <= l && r <= y)
        ev[node].push_back(e);
      else {
        int mid = (l + r) >> 1;
 
        if(x <= mid) Update(node << 1, l, mid, x, y, e);
        if(y > mid) Update(node << 1 | 1, mid + 1, r, x, y, e);
      }
    }
 
    bool DFS(int node, int l, int r) {
      bool ok(true);
      for(Edge e : ev[node]) {
        dsu.Unite(node, e.from, e.to);
      }
 
      if(l == r) {
        for(int fromnode : cola[l]) 
          dsu.ChangeValue(fromnode, true);
        
        for(int tonode : colb[l]) 
          if(!dsu.IsGood(tonode))
            ok = false;
 
        for(int fromnode : cola[l])
          dsu.ChangeValue(fromnode, false);
      } else {
        int mid = (l + r) >> 1;
        ok &= (DFS(node << 1, l, mid) & DFS(node << 1 | 1, mid + 1, r));
      }
 
      dsu.RollBack(node);
      return ok;
    }
};
Segment_Tree aint;
 
int n, m;
bool Solve_Test() {
  bool ok(true);
  scanf("%d%d", &n, &m);
 
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    cola[a[i]].push_back(i);
  }
 
  for(int i = 1; i <= n; i++) {
    scanf("%d", &b[i]); 
    colb[b[i]].push_back(i);
 
    if(b[i] > a[i]) ok = false;
  }
 
  for(int i = 1; i <= m; i++) 
    scanf("%d%d", &ve[i].from, &ve[i].to);
  
  if(ok == false) return false;
  
  aint.Init(n, m);
  for(int i = 1; i <= m; i++)
    aint.Update(1, 1, n, max(b[ve[i].from], b[ve[i].to]), min(a[ve[i].from], a[ve[i].to]), ve[i]);
  return aint.DFS(1, 1, n);
}
 
void Clear() { 
  for(int i = 0; i <= n; i++) {
    a[i] = b[i] = 0;
    cola[i].clear(); colb[i].clear();
  }
 
  for(int i = 0; i <= m; i++)
    ve[i] = Edge{0, 0};
}
 
int main() {
  int t;
  cin >> t;
  
  for(int i = 1; i <= t; i++) {
    cout << Solve_Test() << '\n'; 
    Clear();
  }
  return 0;
}

Compilation message (stderr)

colors.cpp: In member function 'void Segment_Tree::Init(int, int)':
colors.cpp:138:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |       for(int i = 0; i < ev.size(); i++)
      |                      ~~^~~~~~~~~~~
colors.cpp: In function 'bool Solve_Test()':
colors.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:187:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
colors.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |     scanf("%d", &b[i]);
      |     ~~~~~^~~~~~~~~~~~~
colors.cpp:199:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |     scanf("%d%d", &ve[i].from, &ve[i].to);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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