• 欢迎光临~

# CF1697F

• (a_ile a_{i+1})，等价于「对于所有的 (v)，若 (a_ige v)，则 (a_{i+1}ge v)」。
• (a_ine x)，等价于「若 (a_ige x)，则 (a_ige x+1)」。
• (a_i+a_jle x)，等价于「对于所有的 (v)，若 (a_ige v)，则 (¬(a_jge x-v+1))」。
• (a_i+a_jge x)，等价于「对于所有的 (v)，若 (¬(a_ige v))，则 (a_jge x-v+1)」。

• (a_ige v)，则 (a_ige v-1)

Code：

``````#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 360005;
int T;
int n, m, k;
int dfn[N], low[N], tim;
int stk[N], top; bool vis[N];
int bel[N], scc_cnt;
vector <int> G[N];

void addedge(int x, int y) { G[x].pb(y); if (x != (y ^ 1)) G[y ^ 1].pb(x ^ 1); }
int num(int id, int x, bool y) { return ((id - 1) * (k - 1) + (x - 2)) << 1 | y; }
void build(int x) { for (int i = 2; i < k; ++i) addedge(num(x, i, 0), num(x, i + 1, 0)); }
void le(int x, int y) { for (int i = 2; i <= k; ++i) addedge(num(x, i, 1), num(y, i, 1)); }

void ne(int x, int val) {
if (val == 1) addedge(num(x, 2, 0), num(x, 2, 1));
else if (val == k) addedge(num(x, k, 1), num(x, k, 0));
else addedge(num(x, val, 1), num(x, val + 1, 1));
}

void sumle(int x, int y, int val) {
for (int i = 2; i <= k; ++i) {
if (i >= val) addedge(num(x, i, 1), num(x, i, 0)), addedge(num(y, i, 1), num(y, i, 0));
else if (i + k > val) addedge(num(x, i, 1), num(y, val - i + 1, 0));
}
}

void sumge(int x, int y, int val) {
for (int i = 2; i <= k; ++i) {
if (i + k <= val) addedge(num(x, i, 0), num(x, i, 1)), addedge(num(y, i, 0), num(y, i, 1));
else if (i < val) addedge(num(x, i, 0), num(y, val - i + 1, 1));
}
}

void Tarjan(int u) {
dfn[u] = low[u] = ++tim, vis[stk[++top] = u] = 1;
for (int v : G[u]) {
if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++scc_cnt;
do {
bel[stk[top]] = scc_cnt;
vis[stk[top]] = 0;
--top;
} while (stk[top + 1] ^ u);
}
}

void solve() {
scanf("%d%d%d", &n, &m, &k);
int tot = (k - 1) * n * 2;
for (int i = 0; i < tot; ++i) G[i].clear();
for (int i = 1; i <= n; ++i) build(i);
for (int i = 1; i < n; ++i) le(i, i + 1);
for (int i = 1, ty, x, y, val; i <= m; ++i) {
scanf("%d", &ty);
if (ty == 1) scanf("%d%d", &x, &val), ne(x, val);
if (ty == 2) scanf("%d%d%d", &x, &y, &val), sumle(x, y, val);
if (ty == 3) scanf("%d%d%d", &x, &y, &val), sumge(x, y, val);
}
memset(dfn, 0, sizeof (int) * tot), memset(bel, 0, sizeof (int) * tot), tim = top = scc_cnt = 0;
for (int i = 0; i < tot; ++i) if (!dfn[i]) Tarjan(i);
for (int i = 0; i < tot; i += 2) if (bel[i] == bel[i ^ 1]) return printf("%dn", -1), void();
for (int i = 1; i <= n; ++i) {
int val = 1;
for (int j = 2; j <= k; ++j) if (bel[num(i, j, 1)] < bel[num(i, j, 0)]) val = j;
printf("%d ", val);
}
printf("n");
}

int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}
``````