简述

突然记起来 CSP 前特别喜欢的 POI 题还有一堆没写，所以就有了这个坑。

「POI2015」TRZ

写起来还挺麻烦。

我们考虑先把条件写出来：

\[ \begin{cases} s_r^1 – s_{l – 1}^1 \neq s_r^2 – s_{l – 1}^2 \neq s_r^2 – s_{l – 1}^2 \neq s_r^1 – s_{l – 1}^1 \end{cases} \]

进行移项之后发现可以做成自身的特征：

\[ \begin{cases} s_r^1 – s_r^2 \neq s_{l – 1}^1 – s_{l – 1}^2 \\ s_r^1 – s_r^3 \neq s_{l – 1}^1 – s_{l – 1}^3 \\ s_r^2 – s_r^3 \neq s_{l – 1}^2 – s_{l – 1}^3 \end{cases} \]

我们需要找到最长的区间使得这个条件成立，那么其实这就是一个偏序问题。每一个三维的点每一维直接做成其特征即可。而这个偏序需要知道除自己以外的所有信息，所以不能像正常的偏序来搞。所以，我们来进行拼凑。考虑按 \(x\) 排序，然后把 \(y\) 插入权值线段树，最后每个节点维护两个不同的 \(z\) 的极点位置即可。有点难写。

// P3590.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, INF = 0x3f3f3f3f;

int n, ans, ptot = 1;
char str[MAX_N];

struct node
{
    int lson, rson, max_val[2] = {-1, -1}, min_val[2] = {INF, INF};
} nodes[MAX_N * 3];

struct package
{
    int id, x, y, z;
    bool operator<(const package &rhs) const { return x < rhs.x; }
} pre[MAX_N], ai[MAX_N], bi[MAX_N];

int update(int qx, int l, int r, int p, package val)
{
    if (p == 0)
        p = ++ptot;
    if (nodes[p].min_val[0] > val.id)
    {
        if (nodes[p].min_val[0] != INF && bi[nodes[p].min_val[0]].id != val.z)
            nodes[p].min_val[1] = nodes[p].min_val[0];
        nodes[p].min_val[0] = val.id;
    }
    else if (nodes[p].min_val[1] > val.id && bi[nodes[p].min_val[0]].z != val.z)
        nodes[p].min_val[1] = val.id;
    if (nodes[p].max_val[0] < val.id)
    {
        if (nodes[p].max_val[0] != -1 && bi[nodes[p].max_val[0]].z != val.z)
            nodes[p].max_val[1] = nodes[p].max_val[0];
        nodes[p].max_val[0] = val.id;
    }
    else if (nodes[p].max_val[1] < val.id && bi[nodes[p].max_val[0]].z != val.z)
        nodes[p].max_val[1] = val.id;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[p].lson, val);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[p].rson, val);
    return p;
}

int query(int ql, int qr, int l, int r, int p, package val)
{
    if (p == 0)
        return 0;
    if (ql <= l && r <= qr)
    {
        int min_val, max_val;
        if (nodes[p].min_val[0] == INF)
            return 0;
        min_val = (val.z == bi[nodes[p].min_val[0]].z) ? nodes[p].min_val[1] : nodes[p].min_val[0];
        max_val = (val.z == bi[nodes[p].max_val[0]].z) ? nodes[p].max_val[1] : nodes[p].max_val[0];
        if (min_val == INF || max_val == -1)
            return 0;
        return max(abs(val.id - min_val), abs(val.id - max_val));
    }
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid)
        ret = max(ret, query(ql, qr, l, mid, nodes[p].lson, val));
    if (mid < qr)
        ret = max(ret, query(ql, qr, mid + 1, r, nodes[p].rson, val));
    return ret;
}

int main()
{
    scanf("%d%s", &n, str);
    for (int i = 0, ptr = 0; i < n; i++)
    {
        if (str[i] != str[ptr])
            ptr = i;
        ans = max(ans, i - ptr + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (str[i - 1] == 'C')
            pre[i].x++;
        if (str[i - 1] == 'B')
            pre[i].y++;
        if (str[i - 1] == 'S')
            pre[i].z++;
    }
    int lower = 0;
    for (int i = 1; i <= n; i++)
    {
        ai[i].x = pre[i].x - pre[i].y;
        ai[i].y = pre[i].x - pre[i].z;
        ai[i].z = pre[i].y - pre[i].z;
        lower = min(lower, min(ai[i].x, min(ai[i].y, ai[i].z)));
        ai[i].id = i;
    }
    n++;
    for (int i = 1; i <= n; i++)
        ai[i].x -= lower - 1, ai[i].y -= lower - 1, ai[i].z -= lower - 1;
    for (int i = 1; i <= n; i++)
        bi[i] = ai[i];
    bi[0] = bi[n], sort(ai + 1, ai + 1 + n);
    int domain = n - lower + 1;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        if (ai[i].x != ai[ptr].x)
            ptr = i;
        if (ai[i].x != ai[i + 1].x)
        {
            for (int j = ptr; j <= i; j++)
                ans = max(ans, max(query(1, ai[j].y - 1, 1, domain, 1, ai[j]), query(ai[j].y + 1, domain, 1, domain, 1, ai[j])));
            for (int j = ptr; j <= i; j++)
                update(ai[j].y, 1, domain, 1, ai[j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

「POI2009」LYZ

之前没学过 Hall 定理，后面发现结论还算是比较显然的：对于任意的左部点集 \(U\)，与之相连的极大右部点集 \(S\) 要满足 \(|U| \leq |S|\)。本题在数据范围小的时候显然可以直接二分图匹配做，但是现在的数据并不允许，并要求维护完美匹配性。首先发现最糟情况时存在一个区间 \([l, r]\) 满足：

\[ \sum_{i = l}^r X_i > (r – l + 1 + d) k \]

移项得到：

\[ \sum_{i = l}^r (X_i – k) > d \times k \]

线段树找一段这样的即可。

// P3488.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200;

typedef long long ll;

int n, m, k, d;

struct node
{
    ll lft, rig, sum, seg;
} nodes[MAX_N << 2];

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void pushup(int p)
{
    nodes[p].sum = nodes[lson].sum + nodes[rson].sum;
    nodes[p].lft = max(nodes[lson].lft, nodes[lson].sum + nodes[rson].lft);
    nodes[p].rig = max(nodes[rson].rig, nodes[rson].sum + nodes[lson].rig);
    nodes[p].seg = max(nodes[lson].rig + nodes[rson].lft, max(nodes[lson].seg, nodes[rson].seg));
}

void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p] = node{0, 0, -k, -k};
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p);
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r)
    {
        nodes[p].sum += val, nodes[p].seg += val;
        nodes[p].lft = nodes[p].rig = max(0LL, nodes[p].sum);
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    pushup(p);
}

#undef mid
#undef rson
#undef lson

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &d), build(1, n, 1);
    for (int i = 1; i <= m; i++)
    {
        int xpos, val;
        scanf("%d%d", &xpos, &val), update(xpos, 1, n, 1, val);
        puts(nodes[1].seg <= 1LL * d * k ? "TAK" : "NIE");
    }
    return 0;
}

「POI2014」KAR

想起在纪中做过的一道 A 组 SB 题，跟这个比较一致。发现区间之间可以直接维护，那么就上个线段树就好了。

// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

inline void pushup(int p, int l, int r)
{
    nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
    for (register int a = 0; a < 2; a++)
        for (register int b = 0; b < 2; b++)
            for (register int c = 0; c < 2; c++)
                for (register int d = 0; d < 2; d++)
                    nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}

inline void update(int qx, int l, int r, int p)
{
    if (l == r)
        return;
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    pushup(p, l, r);
}

inline void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p][0][0] = nodes[p][1][1] = true;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p, l, r);
}

#undef mid
#undef rson
#undef lson

int main()
{
    n = read();
    for (register int i = 1; i <= n; i++)
        ai[i][0] = read(), ai[i][1] = read();
    q = read(), build(1, n, 1);
    while (q--)
    {
        int x = read(), y = read();
        swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
        update(x, 1, n, 1), update(y, 1, n, 1);
        puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
    }
    return 0;
}

「POI2014」KLO

我们考虑相间而放，用一个堆以大小为关键字来维护可选项。注意的是，我们尽量把和末尾颜色相同的 block 放前。每次选出最大的块、或者是次大的块放置，然后再 check 即可。

// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

inline void pushup(int p, int l, int r)
{
    nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
    for (register int a = 0; a < 2; a++)
        for (register int b = 0; b < 2; b++)
            for (register int c = 0; c < 2; c++)
                for (register int d = 0; d < 2; d++)
                    nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}

inline void update(int qx, int l, int r, int p)
{
    if (l == r)
        return;
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    pushup(p, l, r);
}

inline void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p][0][0] = nodes[p][1][1] = true;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p, l, r);
}

#undef mid
#undef rson
#undef lson

int main()
{
    n = read();
    for (register int i = 1; i <= n; i++)
        ai[i][0] = read(), ai[i][1] = read();
    q = read(), build(1, n, 1);
    while (q--)
    {
        int x = read(), y = read();
        swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
        update(x, 1, n, 1), update(y, 1, n, 1);
        puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
    }
    return 0;
}

「POI2010」Monotonicity

首先我们可以把符号序列给倍长出来，然后再考虑用子序列匹配那一套进行 DP。而这里只需要单维，也就是说我们并不记录子序列的长度，因为可以注意到最长的答案中间切掉，也是满足最优子结构的（证明），所以可以不用记录，搞个树状数组就完事了。

// BZ2090.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, MAX_M = 5e6 + 200;

int n, m, ai[MAX_N], nodes[3][MAX_M], dp[MAX_N];
char str[MAX_N];

inline int lowbit(int x) { return x & (-x); }

void update(int idx, int x, int d)
{
    for (; x < MAX_M; x += lowbit(x))
        nodes[idx][x] = max(nodes[idx][x], d);
}

int query(int idx, int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = max(ret, nodes[idx][x]);
    return ret;
}

int main()
{
    char tmp[2];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= m; i++)
        scanf("%s", tmp), str[i] = tmp[0];
    for (int i = m + 1; i <= n; i++)
        str[i] = str[(i - 1) % m + 1];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(nodes[2][ai[i]], max(query(0, ai[i] - 1), query(1, MAX_M - ai[i]))) + 1;
        ans = max(ans, dp[i]);
        if (str[dp[i]] == '=')
            nodes[2][ai[i]] = max(nodes[2][ai[i]], dp[i]);
        else if (str[dp[i]] == '<')
            update(0, ai[i], dp[i]);
        else
            update(1, MAX_M - ai[i] + 1, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

「POI2005」DWA-Two Parties

这道题就很骚了。

首先有个结论，就是一定能找出一个划分方案，使得某个集合中所有的点都连上了偶数条边，且是最优解。知道这个，我们可以尝试给每个点表一个状态 \(x_i\)，代表其集合 ID（0/1）。这样我们可以搞成一个异或方程组，然后高斯消元得到一个方案即可。

// P3429.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 220;

int n, deg[MAX_N], mat[MAX_N][MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1, tot, v; i <= n; i++)
    {
        scanf("%d", &tot);
        while (tot--)
            scanf("%d", &v), mat[i][v] = 1, deg[i]++;
        if (deg[i] & 1)
            mat[i][i] = mat[i][n + 1] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        int key = i;
        for (int j = i + 1; j <= n; j++)
            if (mat[j][i] != 0)
            {
                key = j;
                break;
            }
        if (key != i)
            for (int j = i; j <= n + 1; j++)
                swap(mat[i][j], mat[key][j]);
        for (int j = i + 1; j <= n; j++)
            if (mat[j][i] == 1)
                for (int k = i; k <= n + 1; k++)
                    mat[j][k] ^= mat[i][k];
    }
    mat[n][n] = 1;
    // reverse;
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = i + 1; j <= n; j++)
            if (mat[i][j] != 0)
                for (int k = j; k <= n + 1; k++)
                    mat[i][k] ^= mat[j][k];
        mat[i][i] = 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++)
        tot += mat[i][n + 1];
    printf("%d\n", tot);
    for (int i = 1; i <= n; i++)
        if (mat[i][n + 1])
            printf("%d ", i);
    puts("");
    return 0;
}

「POI2012」STU-Well

大概思路：首先二分那个差值，然后我们再来算每个位置归零的代价，再找最小的位置即可。

那么我们如何快速计算每个位置归零的代价呢？首先我们可以计算让全局合法的最小代价，方式是正反各扫一遍，保证 \(|a_i – a_{i + 1}| \leq mid\)。枚举 \(k\) 时，我们可以分左右来算贡献。以左侧为例，找到一个位置 \(a_{L} > (k – L)mid\)，那么 \([L, i – 1]\) 这一部分的和减去等差数列之和就是部分贡献了。我想了一会为什么这样是对的，发现：如果 \(a_{L} > (k – L)mid\)，且即使这段区间不是等差的，那么这段区间和减去等差数列之和，「多扣」的部分会从 \(a_L\) 上扣除。右侧原理一致。

// P3534.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1e6 + 200;

int n;
ll m, xi[MAX_N], ai[MAX_N], pre[MAX_N], prefix[MAX_N], suffix[MAX_N];

int check(int mid)
{
    ai[1] = xi[1];
    for (int i = 2; i <= n; i++)
        ai[i] = min(ai[i - 1] + mid, xi[i]);
    for (int i = n - 1; i >= 1; i--)
        ai[i] = min(ai[i + 1] + mid, ai[i]);
    ll acc = 0;
    for (int i = 1; i <= n; i++)
        acc += xi[i] - ai[i], pre[i] = pre[i - 1] + ai[i];
    if (acc > m)
        return 0;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        while (ptr < i && ai[ptr] <= 1LL * (i - ptr) * mid)
            ptr++;
        prefix[i] = pre[i - 1] - pre[ptr - 1] - 1LL * (i - ptr) * (i - ptr + 1) / 2 * mid;
    }
    for (int i = n, ptr = n; i >= 1; i--)
    {
        while (ptr > i && ai[ptr] <= 1LL * (ptr - i) * mid)
            ptr--;
        suffix[i] = pre[ptr] - pre[i] - 1LL * (ptr - i) * (ptr - i + 1) / 2 * mid;
    }
    for (int i = 1; i <= n; i++)
        if (prefix[i] + suffix[i] + acc + ai[i] <= m)
            return i;
    return 0;
}

int main()
{
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &xi[i]);
    int l = 0, r = 1e9, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    printf("%d %d\n", check(res), res);
    return 0;
}

「POI2014」PAN-Solar Panels

题目大概就是要求你在二维平面上，找到一个最大的 \(d\) 使得刚好 \(x = kd, y = kd\) 在这个矩形内有交点。发现有交点的条件是：

\[ \lfloor \frac{smax}{d} \rfloor – \lfloor \frac{smin – 1}{d} \rfloor > 0 \\ \lfloor \frac{wmax}{d} \rfloor – \lfloor \frac{wmin – 1}{d} \rfloor > 0 \]

那可以直接搞搞整除分块，每次取右端点做答案即可。

// P3579.cpp
#include <bits/stdc++.h>

using namespace std;

int T, smin, smax, wmin, wmax;

inline char nc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        smin = read(), smax = read(), wmin = read(), wmax = read();
        smin--, wmin--;
        int ans = 0;
        for (int d = 1, gx; d <= min(smax, wmax); d = gx + 1)
        {
            gx = min({smax / (smax / d), wmax / (wmax / d)});
            if (int(smin / d) != 0)
                gx = min(gx, smin / (smin / d));
            if (int(wmin / d) != 0)
                gx = min(gx, wmin / (wmin / d));
            if ((smax / d) - (smin / d) > 0 && (wmax / d) - (wmin / d) > 0)
                ans = gx;
        }
        printf("%d\n", ans);
    }
    return 0;
}

「POI2015」PUS

经典的线段树优化建图，暴力拆成 \(k + 1\) 个区间之后跑 DAG DP 即可。

// P3588.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 6e5 + 200, MAX_E = 8e6 + 200;

int n, s, m, dp[MAX_N], head[MAX_N], current, sidx[MAX_N], ptot, deg[MAX_N], topoidx[MAX_N], topotot;
bool isFixed[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_E];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++, deg[dst]++;
}

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    ptot = max(ptot, p);
    if (l == r)
        return (void)(sidx[l] = p);
    addpath(p, lson, 0), addpath(p, rson, 0);
    build(l, mid, lson), build(mid + 1, r, rson);
}

void update(int ql, int qr, int l, int r, int p, int src)
{
    if (ql > qr)
        return;
    if (ql <= l && r <= qr)
        return (void)(addpath(src, p, 0));
    if (ql <= mid)
        update(ql, qr, l, mid, lson, src);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, src);
}

#undef mid
#undef rson
#undef lson

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &s, &m), build(1, n, 1);
    for (int i = 1; i <= n; i++)
        dp[sidx[i]] = 1;
    for (int i = 1, p, d; i <= s; i++)
        scanf("%d%d", &p, &d), dp[sidx[p]] = d, isFixed[sidx[p]] = true;
    while (m--)
    {
        int l, r, k, cpt, last = l - 1;
        scanf("%d%d%d", &l, &r, &k), cpt = ++ptot, last = l - 1;
        for (int i = 1, pt; i <= k; i++)
            scanf("%d", &pt), addpath(sidx[pt], cpt, 1), update(last + 1, pt - 1, 1, n, 1, cpt), last = pt;
        update(last + 1, r, 1, n, 1, cpt);
    }
    queue<int> q;
    for (int i = 1; i <= ptot; i++)
        if (deg[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), topoidx[++topotot] = u;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (--deg[edges[i].to] == 0)
                q.push(edges[i].to);
    }
    for (int i = 1; i <= ptot; i++)
        if (deg[i] != 0)
            puts("NIE"), exit(0);
    for (int id = ptot; id >= 1; id--)
    {
        int u = topoidx[id], max_val = 1;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            max_val = max(max_val, dp[edges[i].to] + edges[i].weight);
        if (isFixed[u] && max_val > dp[u])
            puts("NIE"), exit(0);
        else if (!isFixed[u])
            dp[u] = max_val;
    }
    for (int i = 1; i <= n; i++)
        if (dp[sidx[i]] > 1e9 || dp[sidx[i]] < 1)
            puts("NIE"), exit(0);
    puts("TAK");
    for (int i = 1; i <= n; i++)
        printf("%d%c", dp[sidx[i]], " \n"[i == n]);
    return 0;
}