Submission #198426

#	Time	Username	Problem	Language	Result	Execution time	Memory
198426		model_code	Colors (RMI18_colors)	C++14	100 / 100	1288 ms	78516 KiB

colors

// 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 (stderr)

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 / 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