oj.uz

Submission #646239

# Submission time Handle Problem Language Result Execution time Memory
646239 2022-09-29T09:38:08 Z Matteo_Verz Colors (RMI18_colors) C++17
100 / 100
 615 ms 87576 KB 
/*
                `-/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

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

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8772 KB Output is correct
2 Correct 29 ms 7944 KB Output is correct
3 Correct 7 ms 7856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9136 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 8768 KB Output is correct
2 Correct 31 ms 7968 KB Output is correct
3 Correct 8 ms 7764 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 8768 KB Output is correct
2 Correct 31 ms 7968 KB Output is correct
3 Correct 8 ms 7764 KB Output is correct
4 Correct 179 ms 10452 KB Output is correct
5 Correct 377 ms 34276 KB Output is correct
6 Correct 609 ms 65332 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8772 KB Output is correct
2 Correct 29 ms 7944 KB Output is correct
3 Correct 7 ms 7856 KB Output is correct
4 Correct 82 ms 8768 KB Output is correct
5 Correct 31 ms 7968 KB Output is correct
6 Correct 8 ms 7764 KB Output is correct
7 Correct 79 ms 8776 KB Output is correct
8 Correct 29 ms 7980 KB Output is correct
9 Correct 8 ms 7752 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 10452 KB Output is correct
2 Correct 407 ms 35244 KB Output is correct
3 Correct 390 ms 64852 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8188 KB Output is correct
2 Correct 16 ms 8048 KB Output is correct
3 Correct 9 ms 7636 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8772 KB Output is correct
2 Correct 29 ms 7944 KB Output is correct
3 Correct 7 ms 7856 KB Output is correct
4 Correct 75 ms 9136 KB Output is correct
5 Correct 82 ms 8768 KB Output is correct
6 Correct 31 ms 7968 KB Output is correct
7 Correct 8 ms 7764 KB Output is correct
8 Correct 179 ms 10452 KB Output is correct
9 Correct 377 ms 34276 KB Output is correct
10 Correct 609 ms 65332 KB Output is correct
11 Correct 79 ms 8776 KB Output is correct
12 Correct 29 ms 7980 KB Output is correct
13 Correct 8 ms 7752 KB Output is correct
14 Correct 160 ms 10452 KB Output is correct
15 Correct 407 ms 35244 KB Output is correct
16 Correct 390 ms 64852 KB Output is correct
17 Correct 37 ms 8188 KB Output is correct
18 Correct 16 ms 8048 KB Output is correct
19 Correct 9 ms 7636 KB Output is correct
20 Correct 101 ms 9904 KB Output is correct
21 Correct 379 ms 38936 KB Output is correct
22 Correct 615 ms 87576 KB Output is correct