QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#837547#9772. Permutation Routingnhuang685WA 62ms3852kbC++234.1kb2024-12-30 07:07:462024-12-30 07:07:46

Judging History

你现在查看的是最新测评结果

  • [2025-01-10 11:38:24]
  • hack成功,自动添加数据
  • (/hack/1438)
  • [2024-12-30 07:07:46]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:3852kb
  • [2024-12-30 07:07:46]
  • 提交

answer

/**
 * @author n685
 * @date 2024-12-29 16:25:30
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

void solve() {
  int n;
  std::cin >> n;

  std::vector<int> p(n);
  for (int& v : p) {
    std::cin >> v;
    --v;
  }

  std::vector<std::vector<std::pair<int, int>>> adj(n);
  std::vector<std::pair<int, int>> edges;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    std::cin >> u >> v;
    --u;
    --v;
    adj[u].emplace_back(i, v);
    adj[v].emplace_back(i, u);
    edges.emplace_back(u, v);
  }

  std::vector<std::vector<int>> ans;
  auto apply = [&](std::vector<int> v) {
    rs::sort(v);
    v.erase(rs::unique(v).begin(), v.end());
    if (v.empty()) {
      return;
    }
    ans.push_back(v);
    for (int i : v) {
      std::swap(p[edges[i].first], p[edges[i].second]);
    }
  };

  std::vector<int> sub(n), rem(n);
  auto comp_sub = [&](auto&& self, int node, int par) -> void {
    sub[node] = 1;
    for (auto [t, i] : adj[node]) {
      if (i == par || rem[i]) {
        continue;
      }
      self(self, i, node);
      sub[node] += sub[i];
    }
  };
  auto cent = [&](auto&& self, int node, int par, int sz) -> int {
    for (auto [t, i] : adj[node]) {
      if (i == par || rem[i]) {
        continue;
      }
      if (2 * sub[i] > sz) {
        return self(self, i, node, sz);
      }
    }
    return node;
  };

  std::vector<int> bel(n);
  auto comp_bel_dfs = [&](auto&& self, int node, int par, int val) -> void {
    bel[node] = val;
    for (auto [t, i] : adj[node]) {
      if (i != par && !rem[i]) {
        self(self, i, node, val);
      }
    }
  };
  auto comp_bel = [&](int rt) -> void {
    bel[rt] = -1;
    for (auto [t, i] : adj[rt]) {
      if (!rem[i]) {
        comp_bel_dfs(comp_bel_dfs, i, rt, t);
      }
    }
  };
  auto good = [&](int node) -> bool { return bel[node] == bel[p[node]]; };
  auto phase1_dfs
    = [&](auto&& self, int node, int par, std::vector<int>& fl) -> void {
    bool g = good(node);
    for (auto [t, i] : adj[node]) {
      if (i == par || rem[i]) {
        continue;
      }
      if (g && !good(i)) {
        fl.push_back(t);
      }
      self(self, i, node, fl);
    }
  };
  auto phase1 = [&](int rt, std::vector<int>& fl) -> void {
    for (auto [t, i] : adj[rt]) {
      if (!rem[i]) {
        phase1_dfs(phase1_dfs, i, rt, fl);
      }
    }
  };

  auto gen = [&](auto&& self, int rt) -> void {
    comp_sub(comp_sub, rt, -1);
    rt = cent(cent, rt, -1, sub[rt]);
    comp_bel(rt);
    while (true) {
      std::vector<int> fl;
      phase1(rt, fl);
      if (fl.empty()) {
        break;
      }
      apply(fl);
    }
    while (true) {
      std::vector<int> fl1;
      for (auto [t, i] : adj[rt]) {
        if (!rem[i] && !good(i)) {
          fl1.push_back(t);
          break;
        }
      }
      if (fl1.empty()) {
        break;
      }
      phase1(rt, fl1);
      apply(fl1);
      std::vector<int> fl2;
      for (auto [t, i] : adj[rt]) {
        if (!rem[i] && bel[p[rt]] == t) {
          fl2.push_back(t);
          break;
        }
      }
      phase1(rt, fl2);
      if (!fl2.empty()) {
        apply(fl2);
      }
    }
    rem[rt] = true;
    for (auto [t, i] : adj[rt]) {
      if (!rem[i]) {
        self(self, i);
      }
    }
  };
  gen(gen, 0);
  std::cout << ans.size() << '\n';
  for (const auto& v : ans) {
    std::cout << v.size();
    for (int i : v) {
      std::cout << ' ' << i + 1;
    }
    std::cout << '\n';
  }
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3768kb

input:

1
5
1 4 2 5 3
1 2
2 3
2 4
1 5

output:

7
1 4
1 1
1 2
1 1
1 3
1 1
1 4

result:

ok ok, up to 7 steps were used

Test #2:

score: 0
Accepted
time: 18ms
memory: 3852kb

input:

10000
5
2 3 1 5 4
1 5
3 2
1 2
1 4
5
1 2 3 4 5
2 3
3 4
2 1
4 5
5
4 2 5 1 3
3 5
2 3
4 1
3 1
5
1 3 4 2 5
5 3
2 1
1 3
2 4
5
1 2 3 4 5
2 1
3 5
2 3
5 4
5
1 2 3 4 5
4 5
3 4
4 2
4 1
5
5 2 1 4 3
2 1
5 1
3 1
1 4
5
4 1 2 5 3
3 1
5 1
1 2
1 4
5
5 3 4 2 1
3 1
3 5
4 3
3 2
5
3 4 1 2 5
3 2
3 5
1 5
3 4
5
3 4 1 2 5
2 ...

output:

5
1 2
1 1
1 4
1 1
1 3
0
2
1 1
1 3
4
1 2
1 3
1 2
1 4
0
0
2
1 2
1 3
8
1 1
1 3
1 1
1 4
1 1
1 1
1 2
1 1
5
1 1
1 2
1 1
1 3
1 4
6
1 3
1 1
1 4
1 1
1 2
1 3
3
1 2
2 1 4
1 2
3
1 1
1 4
1 2
0
9
1 2
1 3
2 1 2
1 4
1 2
1 3
1 2
1 4
1 1
6
1 1
1 3
1 1
1 2
1 1
1 3
2
1 2
1 1
0
0
0
6
1 2
1 1
1 2
1 4
1 2
1 1
4
1 1
1 4
1 ...

result:

ok ok, up to 11 steps were used

Test #3:

score: -100
Wrong Answer
time: 62ms
memory: 3784kb

input:

10000
10
2 7 5 6 4 8 3 1 10 9
8 10
6 1
5 6
4 7
10 2
6 8
7 6
5 3
9 8
10
4 10 6 1 8 3 9 5 7 2
3 10
9 10
5 10
4 6
10 8
10 4
7 10
4 2
4 1
10
9 7 5 10 3 8 2 6 1 4
10 3
9 3
6 3
7 3
4 3
2 3
5 2
3 8
3 1
10
10 9 5 6 3 4 8 7 2 1
2 6
7 8
5 2
4 9
9 3
3 8
8 5
6 10
4 1
10
2 1 6 7 10 3 4 9 8 5
10 3
3 5
1 3
3 2
3 9...

output:

14
1 5
1 2
1 6
2 1 2
1 6
1 3
1 7
2 3 4
1 7
1 8
1 5
1 1
1 9
1 1
17
2 4 8
1 1
1 6
2 1 8
1 6
1 1
1 2
1 7
1 2
1 3
1 5
1 3
1 4
1 9
1 4
1 8
1 4
12
1 1
1 5
1 1
1 6
2 2 7
1 9
1 2
1 4
1 3
1 8
1 3
1 6
28
1 2
1 6
1 7
2 3 6
2 1 5
3 4 6 8
2 7 9
2 3 6
2 1 5
2 4 6
1 7
2 3 6
1 5
1 6
1 7
1 6
1 4
1 9
1 4
1 5
1 4
1 9
...

result:

wrong answer vertex 2 appears twice in step 1