Overview

We treat each request as “precedence constraints between tasks” and construct a directed graph consisting only of the requests that are not currently ignored.
If this graph is a DAG (directed acyclic graph), then a valid schedule exists, so we use binary search to find the minimum filter strength \(X_t\) at each time point.

Analysis

If the sequence of request \(j\) is

\(P_{j,1}, P_{j,2}, \ldots, P_{j,K_j}\)

then to satisfy this request, it is sufficient that:

• \(P_{j,1}\) comes before \(P_{j,2}\)
• \(P_{j,2}\) comes before \(P_{j,3}\)
• \(\ldots\)
• \(P_{j,K_j-1}\) comes before \(P_{j,K_j}\)

In other words, request \(j\) can be represented as directed edges:

\(P_{j,1} \to P_{j,2} \to \cdots \to P_{j,K_j}\)

For example, if a request is 3 1 4, we add the constraints:

\(3 \to 1\), \(1 \to 4\)

At this point, whether all requests that must be satisfied can be simultaneously fulfilled can be determined by checking whether the constructed directed graph has a cycle.

• If there is no cycle:
  The topological sort order gives a valid schedule.

• If there is a cycle:
  For example, there is a contradiction like \(a\) must come before \(b\), \(b\) must come before \(c\), and \(c\) must come before \(a\), so no permutation can satisfy all constraints.

Therefore, the problem can be rephrased as follows:

For each time point \(t\), find the minimum \(X\) such that when we build a graph using only the requests with \(W_j > X\), the graph is a DAG.

The key insight here is that as \(X\) increases, more requests can be ignored.

That is:

• If the conditions can be satisfied for some \(X\),
• then they can necessarily be satisfied for any larger \(X\) as well.

This is monotonicity.
Therefore, we can binary search on \(X\) for each \(t\).

However, \(X\) can range over a wide interval from \(0\) to \(10^9\).
In practice, the conditions only change when \(X\) reaches the priority \(W_j\) of some request.

This is because request \(j\):

• must be satisfied when \(W_j > X\)
• can be ignored when \(W_j \leq X\)

Therefore, it suffices to consider only the following as answer candidates:

\(0\) and all \(W_j\)

Algorithm

First, read all requests.
Also, collect the answer candidates:

\(0, W_1, W_2, \ldots, W_M\)

sort them, and remove duplicates.

Next, consider a function topo(t, X).

This function builds a directed graph using only the requests from \(1\) to \(t\) that satisfy \(W_j > X\).

For each request, from the sequence

\(P_{j,1}, P_{j,2}, \ldots, P_{j,K_j}\)

we add edges for adjacent elements:

\(P_{j,i} \to P_{j,i+1}\)

After that, we perform a topological sort.

• If all vertices can be extracted, the graph is a DAG
• If some vertices could not be extracted, a cycle exists

For each \(t = 1, 2, \ldots, M\), we binary search over the candidate array.

• ok: a candidate that satisfies the condition
• ng: a candidate that does not satisfy the condition

and find the minimum ok.

Finally, considering all requests, i.e., for \(t = M\), we perform a topological sort once more using the found \(X_M\).
The resulting order is the schedule to be output.

Complexity

Let \(S = \sum_{j=1}^{M} K_j\).

One topological sort takes time proportional to the number of vertices \(N\) and the number of edges added.
Since the number of edges is at most \(S\), the complexity is \(O(N + S)\).

For each \(t\), we perform binary search, and since there are at most \(M + 1\) candidates, the number of binary search iterations is \(O(\log M)\).

• Time complexity: \(O(M \log M \cdot (N + S))\)
• Space complexity: \(O(N + S + M)\)

Given the constraints \(N \leq 2000\), \(M \leq 1000\), \(S \leq 3000\), this is sufficiently fast.

Implementation Notes

Task numbers are \(1\)-indexed in the input, but are converted to \(0\)-indexed in the implementation for convenience.
When outputting, we add \(1\) back.

In the topological sort, vertices with in-degree \(0\) are pushed into a queue for processing.

if (indeg[i] == 0) q.push(i);

Each time an edge is traversed, the in-degree is decremented, and vertices whose in-degree becomes \(0\) are added to the queue.

If the length of the final obtained order is \(N\), it means all tasks could be arranged, and a valid schedule exists.

Also, the same edge may be added multiple times, but since the in-degree increases accordingly and is also decremented the same number of times during processing, the algorithm works correctly.

Source Code

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

struct Request {
    long long w;
    vector<int> p;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<Request> req(M);
    vector<long long> cand;
    cand.push_back(0);

    for (int j = 0; j < M; j++) {
        int K;
        cin >> req[j].w >> K;
        req[j].p.resize(K);
        for (int i = 0; i < K; i++) {
            cin >> req[j].p[i];
            --req[j].p[i];
        }
        cand.push_back(req[j].w);
    }

    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());

    auto topo = [&](int t, long long X) -> vector<int> {
        vector<vector<int>> g(N);
        vector<int> indeg(N, 0);

        for (int j = 0; j < t; j++) {
            if (req[j].w > X) {
                for (int i = 0; i + 1 < (int)req[j].p.size(); i++) {
                    int u = req[j].p[i];
                    int v = req[j].p[i + 1];
                    g[u].push_back(v);
                    indeg[v]++;
                }
            }
        }

        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (indeg[i] == 0) q.push(i);
        }

        vector<int> ord;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            ord.push_back(v);
            for (int to : g[v]) {
                indeg[to]--;
                if (indeg[to] == 0) q.push(to);
            }
        }

        return ord;
    };

    auto acyclic = [&](int t, long long X) -> bool {
        return (int)topo(t, X).size() == N;
    };

    vector<long long> ans(M);

    for (int t = 1; t <= M; t++) {
        int ok = (int)cand.size() - 1;
        int ng = -1;

        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (acyclic(t, cand[mid])) ok = mid;
            else ng = mid;
        }

        ans[t - 1] = cand[ok];
    }

    for (int i = 0; i < M; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    vector<int> schedule = topo(M, ans[M - 1]);

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << schedule[i] + 1;
    }
    cout << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.