# AGC041E Balancing Network

Author: Fanyi Pu

Published: 2020-03-11

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/agc041-e>

AGC041E Balancing Network 题解。

有 $n$ 条线 $m$ 个平衡器，从左往右第 $i$ 个平衡器连接了 $x_i,y_i$ 条电线（$1\le x_i<y_i\le n$），每个平衡器都有一个状态：向上或向下。考虑一个令牌，从最左边的某一条导线开始，如果在第 $i$ 个位置，如果他在 $x_i$ 导线上且平衡器状态向下，那么就到 $y_i$，同理如果在 $y_i$ 且状态向上，则到 $x_i$。记 $k_i$ 表示令牌从导线 $i$ 开始到无穷远处是他在哪条导线上。

让你构造两种解，每种解用一个字符串表示，表示每个平衡器的状态。第一组解要求所有的 $k_i$ 相等，第二组接要求至少有两个 $k_i$ 不相等。无解输出 $-1$。

数据范围 $2\le n\le 5\times 10^4,\,1\le m\le 10^5$。

一道有趣的构造题。

首先我们考虑构造第一组解。我们考虑从后往前做，枚举 $t$ 判断是否有一组解使得最终所有 $k_i=t$。令 $f_{i,j}$ 表示仅有最后 $i$ 个平衡器时，第 $j$ 条线上的令牌是否到了 $t$。考虑在最前面加一个平衡器。发现其实就是 $f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_j}\vee f_{i,y_{n-i}}$。因为只要有一条线上可以到达 $t$，我们可以将两条线上的令牌都导到这条线上。

考虑上面的做法将第一维滚掉之后是 $\mathcal{O}(m)$ 的，于是我们得到了一个 $\mathcal{O}(nm)$ 的算法。考虑优化，我们令 $g_{i,j,t}$ 表示最后 $i$ 个，第 $j$ 条线是否能到达 $t$。我们考虑转移就是 $g_{i+1,x_{n-i},t}=g_{i+1,y_{n-i},t}=g_{i,x_{n-i},t}\vee g_{i,y_{n-i},t}$。不难发现这个东西可以用 `bitset` 进行优化。常数 $\frac{1}{64}$，可以过。

然后考虑构造，这就简单了，直接沿着一个有解的 $t$，继续做一遍上面的 `dp` 即可。

然后考虑第二问，首先我们发现之后当 $n=2$ 的时候才会发生无解。其余时刻都不会，至于为什么，我们考虑一下的构造方法。

仍然考虑倒着做，$f_{i,j}$ 表示加入最后的 $i$ 个平衡器，第 $j$ 根线上的令牌现在在哪儿。

我们考虑加入一个令牌，那只会有两种状态：$f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_{n-i}}$ 或是 $f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,y_{n-i}}$。而最终的目的是让至少有两个 $f$ 值是不相等的。那么我们考虑 $g_{i,j}$ 表示 $f_{i,k}=j$ 的数量。这样我们只要比较两个 $f$ 的 $g$，看看那个多，让多的给少的一个。考虑到 $n>2$，每次将一个 $g$ 加 $1$，一个 $g$ 减 $1$。不难发现一定有两个 $g$ 是大于 $0$ 的。于是一定有一种方案合法。

[代码](https://atcoder.jp/contests/agc041/submissions/10746815)

```cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline char gc() {
    static const int L = 233333;
    static char sxd[L], *sss = sxd, *ttt = sxd;
    if (sss == ttt) {
        ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
        if (sss == ttt) {
            return EOF;
        }
    }
    return *sss++;
}

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
    char dd;
    for (; !isalpha(c); dd);
    return c;
}

inline char readchar() {
    char dd;
    for (; c == ' '; dd);
    return c;
}

template <class T>
inline bool read(T& x) {
    bool flg = false;
    char dd;
    x = 0;
    for (; !isdigit(c); dd) {
        if (c == '-') {
            flg = true;
        } else if(c == EOF) {
            return false;
        }
    }
    for (; isdigit(c); dd) {
        x = (x * 10) + (c ^ 48);
    }
    if (flg) {
        x = -x;
    }
    return true;
}
#undef dd

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) {
        putchar(x | 48);
        return;
    }
    write(x / 10);
    putchar((x % 10) | 48);
}

template <class T>
inline void writesp(T x) {
    write(x);
    putchar(' ');
}

template <class T>
inline void writeln(T x) {
    write(x);
    puts("");
}

#define lowbit(x) (x & -x)

namespace dfcmd {
    const int maxn = 50005;
    const int maxm = 100005;

    int n, m, T;

    struct Balancer {
        int x, y;
    } bal[maxm];

    char ans[maxm];
    int ff[maxn];

    namespace solve1 {
        bitset<maxn> f[maxn];

        inline void solve() {
            for (int i = 1; i <= n; ++i) {
                f[i][i] = 1;
            }
            for (int i = m; i; --i) {
                f[bal[i].x] = f[bal[i].y] = f[bal[i].x] | f[bal[i].y];
            }
            for (int i = 2; i <= n; ++i) {
                f[1] &= f[i];
            }
            int now = 0;
            for (int i = 1; i <= n; ++i) {
                if (f[1][i]) {
                    now = i;
                    break;
                }
            }
            if (!now) {
                puts("-1");
                return;
            }
            ff[now] = 1;
            for (int i = m; i; --i) {
                if (ff[bal[i].x]) {
                    ans[i] = '^';
                } else {
                    ans[i] = 'v';
                }
                ff[bal[i].x] = ff[bal[i].y] = ff[bal[i].x] | ff[bal[i].y];
            }
            puts(ans + 1);
        }
    }

    namespace solve2 {
        int g[maxn];

        inline void solve() {
            if (n == 2) {
                puts("-1");
                return;
            }
            for (int i = 1; i <= n; ++i) {
                ff[i] = i;
                g[i] = 1;
            }
            for (int i = m; i; --i) {
                if (g[ff[bal[i].x]] < g[ff[bal[i].y]]) {
                    g[ff[bal[i].x]]++, g[ff[bal[i].y]]--;
                    ff[bal[i].y] = ff[bal[i].x];
                    ans[i] = '^';
                } else {
                    g[ff[bal[i].x]]--, g[ff[bal[i].y]]++;
                    ff[bal[i].x] = ff[bal[i].y];
                    ans[i] = 'v';
                }
            }
            puts(ans + 1);
        }
    }

    int Main() {
        read(n), read(m), read(T);
        for (int i = 1; i <= m; ++i) {
            read(bal[i].x), read(bal[i].y);
        }
        if (T == 1) {
            solve1::solve();
        } else {
            solve2::solve();
        }
        return 0;
    }
}

int main() {
    return dfcmd::Main();
}
```