列表

详情

NC14374. Tree Equation

描述

Tired of solving mathematical equations, DreamGrid starts to solve equations related to rooted trees.

Let A and B be two arbitrary  rooted trees and r(T) denotes the root of T. DreamGrid has defined two basic operations:
    1.Addition. T = A + B  is built by merging the two roots r(A),r(B) into a new root r(T).That is the subtrees of A and B  (if any) become the subtrees of r(T).   
     2.Multiplication. T = A · B is built by merging r(B) with each vertex x ∈ A so that all the subtrees of r(B) become new subtrees of x.
The following picture may help you understand the operations.

Given three rooted trees A ,B and C,DreamGrid would like to find two rooted trees X and Y such A·X + B · Y = C .

输入描述

There are multiple test cases. The first line of input contains an integer T , indicating the number of test cases. For each test case:
The first line contains three integers  na,nb and nc (2 ≤ na,nb ≤ nc ≤ 105) -- the number of vertices in rooted tree A,B and C,respectively.
The second line contains na intergers a1,a2,...,ana (0 ≤ ai < i) -- where ai is the parent of the i-th vertex in tree A.
The third line contains nb intergers b1,b2,....bnb  (0 ≤ bi < i) - where bi is the parent of the i-th vertex in tree B.
The fourth line contains nc intergers c1,c2,....cnc  (0 ≤ ci < i) - where ci is the parent of the i-th vertex in tree C.
Note that if ai = 0(bi = 0 or ci = 0),then the i-th vertex is the root of the tree A (B or C)
It is guaranteed that the sum of all nc does not exceed 2×106.

输出描述

For each test case, if you can not find a solution, output "Impossible" (without quotes) in the first line.
Otherwise, output two integers nx and ny (1 ≤ nx,ny ≤ 105) denoting the number of vertices in rooted tree  X and Y in the first line.
Then in the second line, output nx intergers x1,x2,...xnx (0 ≤ xi < i)-- where  xi is the parent of the i-th vertex in tree X.
Then in the third line, output ny intergers y1,y2,...yny (0 ≤ yi < i)-- where  yi is the parent of the i-th vertex in tree Y.
If there are multiple solutions, print any of them.

示例1

输入: 

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

输出: 

Impossible
2 1
0 1
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 660ms, 内存消耗: 37312K, 提交时间: 2019-02-21 17:33:27 

#include <bits/stdc++.h>

#define N 100001
#define ll long long
#define pb push_back
#define pri printf

using namespace std;

const long long MOD = (1e9 + 9) * (1e4 + 7);

struct Item
{
  int id;
  ll vl;
  bool operator < (const Item &temp) const
  {
    return vl < temp.vl;
  }
};

int a[N], b[N], pn = 1e4 + 9;
const int inf = 1e9;
vector<int> ppw[3][N];
int n[3], fa[3][N], siz[3][N];
ll Hass[3][N], ha[2][N];
int hana[2][N];
int cnt[2];
int vis[N], Ti, pos[2][N], num_node[2];
map<ll, int> has;

void dfs(int flag, int id)
{
  int i, j, s, p, q, ret, ip;
  vector<ll> now;
  now.clear();
  siz[flag][id] = 1;
  for (i = 0; i < ppw[flag][id].size(); i++)
  {
    ip = ppw[flag][id][i];
    dfs(flag, ip);
    siz[flag][id] += siz[flag][ip];
    now.pb(Hass[flag][ip]);
  }
  sort(now.begin(), now.end());
  Hass[flag][id] = a[now.size()];
  for (i = 0; i < now.size(); i++)
    Hass[flag][id] = Hass[flag][id] * pn ^ now[i] % MOD;
  Hass[flag][id] = Hass[flag][id] * b[now.size()] % MOD;
}

bool gpr(int flag, int id, int ie, int Ti)
{
  int i, j, s, p, q, ip;
  vector<Item> now[2];
  Item pwl;
  if (ppw[2][id].size() < ppw[2][ie].size())
    return false;
  now[0].clear();
  now[1].clear();
  for (i = 0; i < ppw[2][id].size(); i++)
  {
    ip = ppw[2][id][i];
    pwl.vl = Hass[2][ip];
    pwl.id = ip;
    now[1].pb(pwl);
  }
  sort(now[1].begin(), now[1].end());
  for (i = 0; i < ppw[2][ie].size(); i++)
  {
    ip = ppw[2][ie][i];
    pwl.vl = Hass[2][ip];
    pwl.id = ip;
    now[0].pb(pwl);
  }
  sort(now[0].begin(), now[0].end());
  int u = 0, v;
  for (v = 0; v < now[0].size(); v++)
  {
    while (u < now[1].size() && now[1][u].vl < now[0][v].vl)
      u++;
    if (u >= now[1].size() || now[1][u].vl > now[0][v].vl)
      return false;
    vis[now[1][u].id] = Ti;
    u++;
  }
  now[0].clear();
  for (i = 0; i < ppw[2][id].size(); i++)
  {
    ip = ppw[2][id][i];
    if (vis[ip] != Ti && !gpr(flag, ip, ie, Ti))
      return false;
    if (vis[ip] != Ti)
    {
      pwl.vl = ha[flag][ip];
      now[0].pb(pwl);
    }
  }
  sort(now[0].begin(), now[0].end());
  ha[flag][id] = a[now[0].size()];
  for (i = 0; i < now[0].size(); i++)
    ha[flag][id] = ha[flag][id] * pn ^ now[0][i].vl % MOD;
  ha[flag][id] = ha[flag][id] * b[now[0].size()] % MOD;
  return true;
}

void ou(int flag, int id)
{
  int i, j, s, p, q;
  pos[flag][id] = num_node[flag]++;
  for (i = 0; i < ppw[2][id].size(); i++)
  {
    ou(flag, ppw[2][id][i]);
    fa[flag][pos[flag][ppw[2][id][i]]] = pos[flag][id];
  }
}

int main()
{
  int t;
  vector<Item> now[3];
  Item pwl;
  for (int i = 0; i <= 100000; i++)
  {
    b[i] = rand() + 5;
    a[i] = rand() + 5;
  }
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d%d%d", &n[0], &n[1], &n[2]);
    int i, j, s, p, q, ip, u, v;
    for (i = 0; i < 3; i++)
    {
      for (j = 0; j < n[i]; j++)
        ppw[i][j].clear();
      for (j = 0; j < n[i]; j++)
      {
        scanf("%d", &fa[i][j]);
        fa[i][j]--;
        if (fa[i][j] >= 0)
          ppw[i][fa[i][j]].pb(j);
      }
      dfs(i, 0);
    }
    cnt[0] = cnt[1] = 0;
    has.clear();
    for (i = 0; i < n[2]; i++)
    {
      if (has.count(Hass[2][i]))
        continue;
      has[Hass[2][i]];
      int x = siz[2][i];
      if (1LL * x * siz[0][0] - 1 <= siz[2][0] && (siz[2][0] - x * siz[0][0] + 1) % siz[1][0] == 0)
        hana[0][cnt[0]++] = i;
      if (1LL * x * siz[1][0] - 1 <= siz[2][0] && (siz[2][0] - x * siz[1][0] + 1) % siz[0][0] == 0)
        hana[1][cnt[1]++] = i;
    }
    int For_mj, For_mj_2;
    for (For_mj = 0; For_mj < cnt[0]; For_mj++)
      for (For_mj_2 = 0; For_mj_2 < cnt[1]; For_mj_2++)
      {
        if (1LL * siz[2][hana[0][For_mj]] * siz[0][0] + 1LL * siz[2][hana[1][For_mj_2]] * siz[1][0] - 1 != siz[2][0])
          continue;
        Ti += 2;
        for (j = 0; j < 3; j++)
          now[j].clear();
        for (s = 0; s < ppw[2][0].size(); s++)
        {
          pwl.vl = Hass[2][ppw[2][0][s]];
          pwl.id = ppw[2][0][s];
          now[2].pb(pwl);
        }
        sort(now[2].begin(), now[2].end());
        i = hana[0][For_mj];
        for (j = 0; j < ppw[2][i].size(); j++)
        {
          pwl.vl = Hass[2][ppw[2][i][j]];
          pwl.id = ppw[2][i][j];
          now[0].pb(pwl);
        }
        i = hana[1][For_mj_2];
        for (j = 0; j < ppw[2][i].size(); j++)
        {
          pwl.vl = Hass[2][ppw[2][i][j]];
          pwl.id = ppw[2][i][j];
          now[0].pb(pwl);
        }
        sort(now[0].begin(), now[0].end());
        u = 0;
        for (v = 0; v < now[0].size(); v++)
        {
          while (u < now[2].size() && now[2][u] < now[0][v])
            u++;
          if (u >= now[2].size() || now[0][v] < now[2][u])
            break;
          vis[now[2][u].id] = Ti;
          u++;
        }
        if (v >= now[0].size())
        {
          for (j = 0; j < 2; j++)
          {
            now[0].clear();
            for (v = 0; v < now[2].size(); v++)
            {
              if (vis[now[2][v].id] == Ti)
                continue;
              int ie;
              if (j == 0)
                ie = hana[0][For_mj];
              else
                ie = hana[1][For_mj_2];
              if (gpr(j, now[2][v].id, ie, Ti + j))
              {
                pwl.id = now[2][v].id;
                pwl.vl = ha[j][now[2][v].id];
                now[0].pb(pwl);
              }
            }
            sort(now[0].begin(), now[0].end());
            now[1].clear();
            for (v = 0; v < ppw[j][0].size(); v++)
            {
              pwl.id = ppw[j][0][v];
              pwl.vl = Hass[j][ppw[j][0][v]];
              now[1].pb(pwl);
            }
            sort(now[1].begin(), now[1].end());
            u = 0;
            for (v = 0; v < now[1].size(); v++)
            {
              while (u < now[0].size() && now[0][u] < now[1][v])
                u++;
              if (u >= now[0].size() || now[1][v] < now[0][u])
                break;
              vis[now[0][u].id] = Ti;
              u++;
            }
            if (v < now[1].size())
              break;
          }
          if (j >= 2)
            goto orz;
        }
      }
  orz:
    if (For_mj < cnt[0])
    {
      num_node[0] = num_node[1] = 0;
      ou(0, hana[0][For_mj]);
      ou(1, hana[1][For_mj_2]);
      pri("%d %d\n", siz[2][hana[0][For_mj]], siz[2][hana[1][For_mj_2]]);
      pri("0");
      for (i = 1; i < num_node[0]; i++)
        pri(" %d", fa[0][i] + 1);
      pri("\n");
      pri("0");
      for (i = 1; i < num_node[1]; i++)
        pri(" %d", fa[1][i] + 1);
      pri("\n");
    }
    else
      puts("Impossible");
  }
  return 0;
}

上一题

© 2024 nowcoder.com