QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#837595#9772. Permutation Routingnhuang685WA 68ms3628kbC++235.6kb2024-12-30 08:54:402024-12-30 08:54:41

Judging History

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

  • [2025-01-10 11:38:24]
  • hack成功，自动添加数据
  • (/hack/1438)
  • [2024-12-30 08:54:41]
  • 评测
  • 测评结果：WA
  • 用时：68ms
  • 内存：3628kb
查看
  • [2024-12-30 08:54:40]
  • 提交

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);
  }
  auto sep = [&](int i, int j) {
    return edges[i].first != edges[j].first && edges[i].first != edges[j].second
      && edges[i].second != edges[j].first
      && edges[i].second != edges[j].second;    
  };

  std::vector<std::vector<int>> ans;
  auto apply = [&](std::vector<int> v) {
    if (v.empty()) {
      return;
    }
    rs::sort(v);
    v.erase(rs::unique(v).begin(), v.end());
    if (ans.empty()) {
      for (int i : v) {
        std::swap(p[edges[i].first], p[edges[i].second]);
      }
      ans.push_back(v);
      return;
    }
    ans.emplace_back();
    for (int i : v) {
      std::swap(p[edges[i].first], p[edges[i].second]);
      bool g = true;
      for (int j : ans.end()[-2]) {
        if (!sep(i, j)) {
          g = false;
          break;
        }
      }
      if (g) {
        ans.end()[-2].push_back(i);
      } else {
        ans.back().push_back(i);
      }
    }
    if (ans.back().empty()) {
      ans.pop_back();
    } else if (ans.end()[-2] == ans.back()) {
      ans.pop_back();
      ans.pop_back();
    }
  };

  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, bool cc) -> void {
    bool g = cc && (good(node) || bel[p[node]] == -1);
    for (auto [t, i] : adj[node]) {
      if (i == par || rem[i]) {
        continue;
      }
      bool ch = true;
      if (g && !good(i)) {
        ch = false;
        fl.push_back(t);
        g = false;
      }
      self(self, i, node, fl, ch);
    }
  };
  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, true);
      }
    }
  };

  auto gen = [&](auto&& self, int rt) -> void {
    comp_sub(comp_sub, rt, -1);
    rt = cent(cent, rt, -1, sub[rt]);
    dbg(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 (p[i] != i && !rem[i] && !good(i)) {
          fl1.push_back(t);
          break;
        }
      }
      if (fl1.empty()) {
        for (auto [t, i] : adj[rt]) {
          if (!rem[i] && !good(i)) {
            fl1.push_back(t);
            break;
          }
        }
        // if (fl1.empty()) {
        //   break;
        // }
      }
      bool ep = fl1.empty();
      for (auto [t, i] : adj[rt]) {
        if (!rem[i]) {
          phase1_dfs(phase1_dfs, i, rt, fl1, ep || fl1[0] != t);
        }
      }
      if (fl1.empty()) {
        break;
      }
      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);
      ep = fl2.empty();
      for (auto [t, i] : adj[rt]) {
        if (!rem[i]) {
          phase1_dfs(phase1_dfs, i, rt, fl2, ep || fl2[0] != t);
        }
      }
      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();
  }
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

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

output:

6
2 2 4
1 1
1 2
1 3
1 1
1 4

result:

ok ok, up to 6 steps were used

Test #2:

score: 0
Accepted
time: 19ms
memory: 3552kb

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:

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

result:

ok ok, up to 7 steps were used

Test #3:

score: 0
Accepted
time: 68ms
memory: 3628kb

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:

10
2 2 5
1 6
2 1 2
1 6
1 3
1 7
2 3 4
4 7 8 5 9
1 1
1 9
14
2 1 4
1 6
2 1 8
1 6
1 2
1 7
1 2
1 3
1 5
2 3 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
20
1 2
1 6
2 5 7
3 3 4 6
4 1 5 7 9
4 3 4 6 8
4 1 5 7 9
3 3 4 6
2 5 7
2 6 4
1 9
1 4
1 5
1 4
2 9 1
1 8
1 1
1 3
1 1
1 8
13
1 1
1 2...

result:

ok ok, up to 28 steps were used

Test #4:

score: -100
Wrong Answer
time: 54ms
memory: 3620kb

input:

2500
20
19 16 18 14 10 3 6 8 9 20 11 1 13 5 4 17 12 15 7 2
14 9
11 1
7 16
9 5
3 1
16 19
15 4
6 9
7 2
12 15
8 5
20 19
16 9
18 1
1 17
1 15
13 15
9 10
1 19
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 14
6 10
12 14
9 1
13 1
18 15
7 10
7 12
17 4
4 5
16 9
11 10
18 8
13 19
6 20
2 4
3 4
15 11
8 ...

output:

19
3 6 7 8
2 13 19
3 6 16 18
2 13 19
1 6
2 12 13
2 6 1
2 3 4
1 18
1 13
2 8 3
1 3
1 9
2 3 5
1 14
1 15
1 16
2 10 15
1 16
0
0
43
2 11 13
3 4 14 10
4 6 9 11 13
5 12 19 4 10 14
6 1 18 6 9 11 13
6 5 4 10 12 14 19
6 8 6 9 11 13 18
7 15 4 5 10 12 14 19
7 3 6 8 9 11 13 18
6 4 5 10 12 14 15
5 8 9 11 13 18
5 5...

result:

wrong answer Integer parameter [name=number of steps] equals to 64, violates the range [0, 60]
English 繁體中文 简体中文

伺服器時間: 2025-01-21 12:21:07 | 開源專案