oj.uz

Submission #198422

# Submission time Handle Problem Language Result Execution time Memory
198422 2020-01-26T02:35:38 Z model_code Colors (RMI18_colors) C++14
61 / 100
 3000 ms 494772 KB 
// Handles the tree subtasks (and therefore the line and star subtasks too).
//
// Author: Costin Oncescu
#include <bits/stdc++.h>

using namespace std;

int ANS, N, M, lev[200009], a[200009], b[200009], t[200009][19];
pair < int, int > sgm[200009][19];
vector < int > v[200009], h[200009];

pair < int, int > operator + (pair < int, int > a, pair < int, int > b)
{return {max (a.first, b.first), min (a.second, b.second)};}

void dfs (int nod, int tata)
{
  for (int i=1; (1<<i) <= lev[nod]; i++)
    t[nod][i] = t[t[nod][i - 1]][i - 1],
      sgm[nod][i] = sgm[nod][i - 1] + sgm[t[nod][i - 1]][i - 1];
  for (auto it : v[nod])
    if (it != tata)
      lev[it] = lev[nod] + 1, t[it][0] = nod,
        sgm[it][0] = {max (b[it], b[nod]), min (a[it], a[nod])}, dfs (it, nod);
}

pair < int, int > query (int x, int y)
{
  if (lev[x] > lev[y])
    swap (x, y);
  int df = lev[y] - lev[x];
  pair < int, int > ans = {1, N};
  for (int i=0; (1<<i) <= df; i++)
    if (df & (1 << i))
      ans = ans + sgm[y][i],
        y = t[y][i];
  if (x == y) return ans;
  for (int i=17; i>=0; i--)
    if ((1 << i) <= lev[x] && t[x][i] != t[y][i])
      ans = ans + sgm[x][i],
        ans = ans + sgm[y][i],
        x = t[x][i], y = t[y][i];
  ans = ans + sgm[x][0], ans = ans + sgm[y][0];
  return ans;
}

int main ()
{
  int tests;
  scanf ("%d", &tests);
  while (tests --)
    {
      scanf ("%d %d", &N, &M);
      for (int i=1; i<=N; i++)
        scanf ("%d", &a[i]);
      for (int i=1; i<=N; i++)
        scanf ("%d", &b[i]);
      for (int i=1; i<=M; i++)
        {
          int x, y;
          scanf ("%d %d", &x, &y);
          v[x].push_back (y);
          v[y].push_back (x);
        }
      ANS = 1;
      for (int i=1; i<=N; i++)
        if (b[i] > a[i])
          ANS = 0;
      if (ANS)
        {
          lev[1] = 0, dfs (1, -1);
          for (int i=1; i<=N; i++)
            h[a[i]].push_back (i);
          for (int nod = 1; nod <= N; nod ++)
            {
              bool ok = 0;
              for (auto otherNode : h[b[nod]])
                {
                  auto curr = query (nod, otherNode);
                  if (curr.first <= curr.second)
                    {
                      ok = 1;
                      break;
                    }
                }
              if (!ok)
                {
                  ANS = 0;
                  break;
                }
            }
        }
      for (int i=1; i<=N; i++)
        v[i].clear (), h[i].clear ();
      printf ("%d\n", ANS);
    }
  return 0;
}

Compilation message

colors.cpp: In function 'int main()':
colors.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &tests);
   ~~~~~~^~~~~~~~~~~~~~
colors.cpp:52: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:54:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &a[i]);
         ~~~~~~^~~~~~~~~~~~~
colors.cpp:56:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &b[i]);
         ~~~~~~^~~~~~~~~~~~~
colors.cpp:60: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 84 ms 9720 KB Output is correct
2 Correct 36 ms 9848 KB Output is correct
3 Correct 14 ms 10104 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3262 ms 462944 KB Time limit exceeded

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9720 KB Output is correct
2 Correct 41 ms 9720 KB Output is correct
3 Correct 15 ms 10104 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9720 KB Output is correct
2 Correct 41 ms 9720 KB Output is correct
3 Correct 15 ms 10104 KB Output is correct
4 Correct 175 ms 9848 KB Output is correct
5 Correct 648 ms 26300 KB Output is correct
6 Correct 927 ms 60668 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 9720 KB Output is correct
2 Correct 36 ms 9848 KB Output is correct
3 Correct 14 ms 10104 KB Output is correct
4 Correct 89 ms 9720 KB Output is correct
5 Correct 41 ms 9720 KB Output is correct
6 Correct 15 ms 10104 KB Output is correct
7 Correct 91 ms 9976 KB Output is correct
8 Correct 39 ms 9848 KB Output is correct
9 Correct 14 ms 10104 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 9848 KB Output is correct
2 Correct 465 ms 25336 KB Output is correct
3 Correct 499 ms 54648 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3174 ms 494772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 9720 KB Output is correct
2 Correct 36 ms 9848 KB Output is correct
3 Correct 14 ms 10104 KB Output is correct
4 Execution timed out 3262 ms 462944 KB Time limit exceeded