oj.uz

Submission #198426

# Submission time Handle Problem Language Result Execution time Memory
198426 2020-01-26T02:36:08 Z model_code Colors (RMI18_colors) C++14
100 / 100
 1288 ms 78516 KB 
// Author: Costin Oncescu
#include <bits/stdc++.h>
#include <cassert>

using namespace std;

int N, M, t[200009], sz[200009], a[200009], b[200009];
vector < int > v[200009], h[200009];
vector < pair < int, int > > edges[800009];
bool ANS, canGo[200009];

void add (int nod, int st, int dr, int x, int y, int u, int v)
{
  if (x <= st && dr <= y)
    {
      edges[nod].push_back ({u, v});
      return ;
    }
  int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
  if (x <= mij) add (f1, st, mij, x, y, u, v);
  if (mij < y) add (f2, mij + 1, dr, x, y, u, v);
}

stack < pair < int *, int > > stk;

int getRoot (int x)
{
  while (t[x] != x)
    x = t[x];
  return x;
}

void keepInMind (int &x) {stk.push ({&x, x});}

void addEdge (int x, int y)
{
  x = getRoot (x), y = getRoot (y);
  if (x != y)
    {
      if (sz[x] < sz[y])
        swap (x, y);
      keepInMind (t[y]), t[y] = x;
      keepInMind (sz[x]), sz[x] += sz[y];
    }
}

void rollBack (int oldSize)
{
  while (stk.size () > oldSize)
    {
      auto curr = stk.top ();
      stk.pop ();
      *curr.first = curr.second;
    }
}

void solve (int nod, int st, int dr)
{
  int oldSize = stk.size ();
  for (auto e : edges[nod])
    addEdge (e.first, e.second);
  if (st == dr)
    {
      int x = st;
      for (auto pos : v[x])
        canGo[getRoot (pos)] = 1;
      for (auto pos : h[x])
        if (!canGo[getRoot (pos)])
          ANS = 0;
      for (auto pos : v[x])
        canGo[getRoot (pos)] = 0;
    }
  if (st != dr)
    {
      int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
      solve (f1, st, mij);
      solve (f2, mij + 1, dr);
    }
  rollBack (oldSize);
}

int main ()
{
  int tests, corr = 0, overall = 0;
  scanf ("%d", &tests);
  while (tests --)
    {
      scanf ("%d %d", &N, &M);
      for (int i=1; i<=N; i++)
        scanf ("%d", &a[i]), v[a[i]].push_back (i);
      for (int i=1; i<=N; i++) {
        scanf ("%d", &b[i]), h[b[i]].push_back (i);
        assert((b[i] >= 1 && b[i] <= N) || N == 1);
      }
      for (int i=1; i<=M; i++)
        {
          int x, y;
          scanf ("%d %d", &x, &y);
          int l = max (b[x], b[y]), r = min (a[x], a[y]);
          if (l <= r)
            add (1, 1, N, l, r, x, y);
        }
      ANS = 1;
      for (int i=1; i<=N; i++)
        if (b[i] > a[i])
          ANS = 0;
      for (int i=1; i<=N; i++)
        sz[i] = 1, t[i] = i;
      if (ANS)
        solve (1, 1, N);
      printf ("%d\n", ANS);
      //    corr += ANS, overall ++;
      for (int i=1; i<=4 * N; i++)
        edges[i].clear ();
      for (int i=1; i<=N; i++)
        v[i].clear (), h[i].clear ();
    }
  //fprintf (stderr, "%.5f = %d / %d\n", (double) 100.0 * corr / overall, corr, overall);
  return 0;
}

Compilation message

colors.cpp: In function 'void rollBack(int)':
colors.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (stk.size () > oldSize)
          ~~~~~~~~~~~~^~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:84:14: warning: unused variable 'corr' [-Wunused-variable]
   int tests, corr = 0, overall = 0;
              ^~~~
colors.cpp:84:24: warning: unused variable 'overall' [-Wunused-variable]
   int tests, corr = 0, overall = 0;
                        ^~~~~~~
colors.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &tests);
   ~~~~~~^~~~~~~~~~~~~~
colors.cpp:88:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%d %d", &N, &M);
       ~~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:90:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &a[i]), v[a[i]].push_back (i);
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:92:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &b[i]), h[b[i]].push_back (i);
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:98:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
           scanf ("%d %d", &x, &y);
           ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 28664 KB Output is correct
2 Correct 58 ms 28668 KB Output is correct
3 Correct 29 ms 28920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 28804 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 28536 KB Output is correct
2 Correct 61 ms 28664 KB Output is correct
3 Correct 29 ms 28796 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 28536 KB Output is correct
2 Correct 61 ms 28664 KB Output is correct
3 Correct 29 ms 28796 KB Output is correct
4 Correct 228 ms 28536 KB Output is correct
5 Correct 728 ms 44444 KB Output is correct
6 Correct 1288 ms 66164 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 28664 KB Output is correct
2 Correct 58 ms 28668 KB Output is correct
3 Correct 29 ms 28920 KB Output is correct
4 Correct 121 ms 28536 KB Output is correct
5 Correct 61 ms 28664 KB Output is correct
6 Correct 29 ms 28796 KB Output is correct
7 Correct 128 ms 28536 KB Output is correct
8 Correct 62 ms 28540 KB Output is correct
9 Correct 31 ms 28792 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 28536 KB Output is correct
2 Correct 786 ms 45792 KB Output is correct
3 Correct 691 ms 54928 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 28664 KB Output is correct
2 Correct 43 ms 28920 KB Output is correct
3 Correct 31 ms 28664 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 28664 KB Output is correct
2 Correct 58 ms 28668 KB Output is correct
3 Correct 29 ms 28920 KB Output is correct
4 Correct 123 ms 28804 KB Output is correct
5 Correct 121 ms 28536 KB Output is correct
6 Correct 61 ms 28664 KB Output is correct
7 Correct 29 ms 28796 KB Output is correct
8 Correct 228 ms 28536 KB Output is correct
9 Correct 728 ms 44444 KB Output is correct
10 Correct 1288 ms 66164 KB Output is correct
11 Correct 128 ms 28536 KB Output is correct
12 Correct 62 ms 28540 KB Output is correct
13 Correct 31 ms 28792 KB Output is correct
14 Correct 219 ms 28536 KB Output is correct
15 Correct 786 ms 45792 KB Output is correct
16 Correct 691 ms 54928 KB Output is correct
17 Correct 68 ms 28664 KB Output is correct
18 Correct 43 ms 28920 KB Output is correct
19 Correct 31 ms 28664 KB Output is correct
20 Correct 173 ms 28920 KB Output is correct
21 Correct 677 ms 48924 KB Output is correct
22 Correct 1162 ms 78516 KB Output is correct