제출 #198422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198422		model_code	Colors (RMI18_colors)	C++14	61 / 100	3262 ms	494772 KiB

colors

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22