logoChat01.ai

给你一张 $n$ 个点 $m$ 条边的简单无向连通图，每条边有 可通行 和 不可通行 两种状态，初始...

생성일: 2026년 7월 5일

답변에 사용된 모델 GPT-5.5 Thinking by Chat01

질문

给你一张 nn 个点 mm 条边的简单无向连通图，每条边有 可通行 和 不可通行 两种状态，初始每条边的状态均为不可通行。

第
i(1≤i≤n)i(1\le i\le n) 个点上初始有权值
pip_i，
pp 是一个
1…n1\dots n 的排列。

你可以调用以下两种函数，你的目标是使得
∀1≤i≤n,pi=i\forall 1\le i\le n,p_i=i。调用函数的总次数不能超过
10510^5。

void flip(int id);

功能是改变第
id(1≤id≤m)id(1\le id\le m) 条边的状态。即，可通行变为不可通行，不可通行变为可通行。

vector<int> shuffle(int x);

对于这张图上只保留状态为可通行的边时
x(1≤x≤n)x(1\le x\le n) 所属的连通块，交互库会将这个连通块中所有点的权值
pip_i 均匀随机重排列，然后返回一个长度为
nn 的 vector<int> 表示新的权值
pp，下标为
i(0≤i<n)i(0\le i < n) 的项表示新的
pi+1p_{i+1}。

交互格式
你不需要，也不应该实现 main 函数。

你应确保提交的程序包含头文件 shuffle.h，可在程序开头加入以下代码实现：

#include "shuffle.h"

你应当实现下面的函数：

void solve(int n,int m,std::vector<std::pair<int,int>> edge,std::vector<int> p);

其中，nn，mm 和 pp 的含义如题目所述；edge[i].first 和 edge[i].second 表示第
i+1i+1 条边的两个端点。

solve 被交互库调用完毕后：

如果你没有调用 shuffle 函数，那么你需要保证初始的
pp 满足
∀1≤i≤n,pi=i\forall 1\le i\le n,p_i=i。
否则，你需要保证最后一次 shuffle 函数返回的
pp 满足
∀1≤i≤n,pi=i\forall 1\le i\le n,p_i=i。
如何测试你的程序
在终端下输入如下命令进行编译：

g++ grader.cpp your_code.cpp -o shuffle -O2 -std=c++14

得到可执行文件 shuffle 后输入样例进行测试，如果测试通过将会输出 OK 和两个整数，分别为 flip 次数和 shuffle 次数。样例也在附件中，其输入格式为图的点数、边数、每条边的两个端点和
pp。

数据规模与评分标准
本题采用捆绑测试。

对于所有数据，
2≤n≤10002\le n\le 1000，
n−1≤m≤3000n-1\le m \le 3000。

子任务编号
n=n= 分数
11
100100
1010
22
10001000
9090
其中每个子任务取其中分数倍率最低的测试点，乘上该子任务的满分得到最终分数。

对于子任务
11，若你调用函数总次数不超过
10510^5，则分数倍率为
11，否则为
00。

对于子任务
22，设你调用函数的总次数为
XX，分数倍率
f(X)f(X) 定义如下：

f(X)={1,X≤3×104,(105−X7×104)2,3×104<X<105,0,X≥105.f(X)= \begin{cases} 1, & X\le 3\times 10^4,\\[4pt] \left(\dfrac{10^5-X}{7\times 10^4}\right)^2, & 3\times 10^4 \lt X \lt 10^5,\\[10pt] 0, & X\ge 10^5. \end{cases}

交互库的随机种子是确定的。也就是说，对于一份不含随机性的代码，多次提交的结果是相同的。保证在合法的交互次数内，交互库的运行时间不超过
3s\texttt{3s}。实际的交互库可能与下发的不同。

时间限制：5s5\texttt{s}

空间限制：512MB512 \texttt{MB}

Python

python
import math
def T(k,th=25):
    if k<=th:
        return k*k # exact rough
    a=k//2; b=k-a
    return (a+b*sum(1/i for i in range(1,a+1))) + T(a,th)+T(b,th)
for th in [10,20,25,30,40]:
    print(th,T(1000,th))

Python

python
import math
def H(n): return sum(1/i for i in range(1,n+1))
def T(k):
    if k<=1:return 0
    a=k//2;b=k-a
    return a+b*H(a)+T(a)+T(b)
print(T(1000))

사고

Ensuring identity and correctness in partitioning

I’m setting p to identity after a shuffle, and making sure no unnecessary shuffles happen for already correct vertices. The correctness proof hinges on ensuring each partition and side is consistently labeled, with no mix-ups—ensuring that recursion respects the partitioning. As long as edge states stay clean, it's all good.

Thought for 5m 43s

답변

下面给你一套可提交的思路 + C++14 代码框架。核心做法是：

把原图先取一棵 BFS 生成树，只在树边上操作。递归处理一个连通块 S：

  1. 找一条尽量平衡的树边，把 S 分成 A 和 B。
  2. 如果 A 很小，就直接把 A 里的点逐个精确归位，然后把 A 从当前块中剥离。
  3. 如果 A 不小，就先只保证 A 中所有点拿到的权值都属于 A，不要求顺序正确；之后递归排序 A 和 B。
  4. 小连通块直接用“路径洗牌直到目标点正确”的方式精确排序。

shuffle 的随机性只用于“反复洗直到满足条件”，属于 Las Vegas 型做法。

cpp
#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int N, M;

vector<pair<int,int>> edges_;
vector<vector<pair<int,int>>> fullG;
vector<vector<pair<int,int>>> treeG;
vector<int> treeIds;

vector<int> pval, posOf;
vector<char> edgeOn;
vector<int> edgeMark;
int edgeStamp = 1;

const int SMALL_COMP = 12;
const int EXACT_SIDE = 12;

void update_perm(const vector<int>& q) {
    for (int i = 1; i <= N; i++) {
        pval[i] = q[i - 1];
        posOf[pval[i]] = i;
    }
}

void do_shuffle(int x) {
    vector<int> q = ::shuffle(x);
    update_perm(q);
}

void set_open_edges(const vector<int>& need) {
    ++edgeStamp;
    if (edgeStamp == INT_MAX) {
        fill(edgeMark.begin(), edgeMark.end(), 0);
        edgeStamp = 1;
    }

    for (int id : need) edgeMark[id] = edgeStamp;

    for (int id : treeIds) {
        bool want = (edgeMark[id] == edgeStamp);
        if ((bool)edgeOn[id] != want) {
            flip(id);
            edgeOn[id] = want;
        }
    }
}

vector<int> edges_among_active(const vector<char>& active) {
    vector<int> res;
    for (int id : treeIds) {
        int u = edges_[id].first;
        int v = edges_[id].second;
        if (active[u] && active[v]) res.push_back(id);
    }
    return res;
}

vector<int> get_path_edges(int s, int t, const vector<char>& active) {
    vector<int> par(N + 1, -1), parEdge(N + 1, -1);
    queue<int> q;

    par[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) break;

        for (auto [v, id] : treeG[u]) {
            if (!active[v]) continue;
            if (par[v] != -1) continue;

            par[v] = u;
            parEdge[v] = id;
            q.push(v);
        }
    }

    vector<int> path;
    int cur = t;
    while (cur != s) {
        path.push_back(parEdge[cur]);
        cur = par[cur];
    }

    return path;
}

void dfs_postorder(int u, int fa, const vector<char>& inside, vector<int>& order) {
    for (auto [v, id] : treeG[u]) {
        if (v == fa) continue;
        if (!inside[v]) continue;
        dfs_postorder(v, u, inside, order);
    }
    order.push_back(u);
}

struct SplitResult {
    vector<int> A, B;
    int rootA, rootB;
};

SplitResult choose_split(const vector<int>& S) {
    int k = (int)S.size();

    vector<char> inS(N + 1, 0);
    for (int x : S) inS[x] = 1;

    int bestSmall = -1;
    int bestU = -1, bestV = -1, bestEdge = -1;

    function<int(int,int)> dfs = [&](int u, int fa) {
        int sz = 1;

        for (auto [v, id] : treeG[u]) {
            if (v == fa) continue;
            if (!inS[v]) continue;

            int sub = dfs(v, u);
            int small = min(sub, k - sub);

            if (small > bestSmall) {
                bestSmall = small;
                bestU = u;
                bestV = v;
                bestEdge = id;
            }

            sz += sub;
        }

        return sz;
    };

    dfs(S[0], 0);

    vector<int> side1;
    queue<int> q;
    vector<char> vis(N + 1, 0);

    vis[bestV] = 1;
    q.push(bestV);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        side1.push_back(u);

        for (auto [v, id] : treeG[u]) {
            if (!inS[v]) continue;
            if (id == bestEdge) continue;
            if (vis[v]) continue;

            vis[v] = 1;
            q.push(v);
        }
    }

    SplitResult ret;

    if ((int)side1.size() <= k - (int)side1.size()) {
        ret.A = side1;
        ret.rootA = bestV;
        ret.rootB = bestU;

        vector<char> inA(N + 1, 0);
        for (int x : ret.A) inA[x] = 1;

        for (int x : S) {
            if (!inA[x]) ret.B.push_back(x);
        }
    } else {
        vector<char> inSide1(N + 1, 0);
        for (int x : side1) inSide1[x] = 1;

        ret.rootA = bestU;
        ret.rootB = bestV;

        for (int x : S) {
            if (!inSide1[x]) ret.A.push_back(x);
            else ret.B.push_back(x);
        }
    }

    return ret;
}

void exact_sort_component(const vector<int>& S) {
    if (S.size() <= 1) return;

    vector<char> inside(N + 1, 0), active(N + 1, 0);
    for (int x : S) {
        inside[x] = 1;
        active[x] = 1;
    }

    vector<int> order;
    dfs_postorder(S[0], 0, inside, order);

    for (int i = 0; i + 1 < (int)order.size(); i++) {
        int v = order[i];

        if (pval[v] != v) {
            int pos = posOf[v];

            vector<int> path = get_path_edges(v, pos, active);
            set_open_edges(path);

            while (pval[v] != v) {
                do_shuffle(v);
            }
        }

        active[v] = 0;
    }
}

void exact_sort_side(const vector<int>& A, const vector<int>& S, int rootA) {
    vector<char> inA(N + 1, 0), active(N + 1, 0);

    for (int x : A) inA[x] = 1;
    for (int x : S) active[x] = 1;

    vector<int> order;
    dfs_postorder(rootA, 0, inA, order);

    for (int v : order) {
        if (pval[v] != v) {
            int pos = posOf[v];

            vector<int> path = get_path_edges(v, pos, active);
            set_open_edges(path);

            while (pval[v] != v) {
                do_shuffle(v);
            }
        }

        active[v] = 0;
    }
}

void partition_side(const vector<int>& A, const vector<int>& S, int rootA) {
    vector<char> inA(N + 1, 0), active(N + 1, 0);

    for (int x : A) inA[x] = 1;
    for (int x : S) active[x] = 1;

    vector<int> order;
    dfs_postorder(rootA, 0, inA, order);

    for (int v : order) {
        vector<int> nowEdges = edges_among_active(active);
        set_open_edges(nowEdges);

        while (!inA[pval[v]]) {
            do_shuffle(v);
        }

        active[v] = 0;
    }
}

void solve_component(const vector<int>& S) {
    if (S.size() <= 1) return;

    bool already = true;
    for (int x : S) {
        if (pval[x] != x) {
            already = false;
            break;
        }
    }

    if (already) return;

    if ((int)S.size() <= SMALL_COMP) {
        exact_sort_component(S);
        return;
    }

    SplitResult sp = choose_split(S);

    if ((int)sp.A.size() < EXACT_SIDE) {
        exact_sort_side(sp.A, S, sp.rootA);
        solve_component(sp.B);
    } else {
        partition_side(sp.A, S, sp.rootA);
        solve_component(sp.A);
        solve_component(sp.B);
    }
}

vector<int> bfs_dist(int src) {
    vector<int> dist(N + 1, -1);
    queue<int> q;

    dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto [v, id] : fullG[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    return dist;
}

void build_bfs_tree() {
    int center = 1;
    int bestEcc = INT_MAX;

    for (int s = 1; s <= N; s++) {
        vector<int> dist = bfs_dist(s);

        int ecc = 0;
        for (int i = 1; i <= N; i++) {
            ecc = max(ecc, dist[i]);
        }

        if (ecc < bestEcc) {
            bestEcc = ecc;
            center = s;
        }
    }

    vector<int> par(N + 1, -1), parEdge(N + 1, -1);
    queue<int> q;

    par[center] = 0;
    q.push(center);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto [v, id] : fullG[u]) {
            if (par[v] != -1) continue;

            par[v] = u;
            parEdge[v] = id;
            q.push(v);

            treeIds.push_back(id);
            treeG[u].push_back({v, id});
            treeG[v].push_back({u, id});
        }
    }
}

} // namespace

void solve(int n, int m, vector<pair<int,int>> edge, vector<int> p) {
    N = n;
    M = m;

    edges_.assign(M + 1, {0, 0});
    fullG.assign(N + 1, {});
    treeG.assign(N + 1, {});
    edgeOn.assign(M + 1, 0);
    edgeMark.assign(M + 1, 0);

    pval.assign(N + 1, 0);
    posOf.assign(N + 1, 0);

    for (int i = 1; i <= M; i++) {
        int u = edge[i - 1].first;
        int v = edge[i - 1].second;

        edges_[i] = {u, v};
        fullG[u].push_back({v, i});
        fullG[v].push_back({u, i});
    }

    for (int i = 1; i <= N; i++) {
        pval[i] = p[i - 1];
        posOf[pval[i]] = i;
    }

    bool ok = true;
    for (int i = 1; i <= N; i++) {
        if (pval[i] != i) {
            ok = false;
            break;
        }
    }

    if (ok) return;

    build_bfs_tree();

    vector<int> all;
    for (int i = 1; i <= N; i++) all.push_back(i);

    solve_component(all);
}

这份代码的关键调参是：

cpp
const int SMALL_COMP = 12;
const int EXACT_SIDE = 12;

如果本地测出来调用次数偏高，可以试试 10、14、16。一般 10~16 比较稳：
EXACT_SIDE 越小，越倾向于做集合划分；越大，越倾向于直接精确归位。

이 Q&A 공유하기