打卡

题目链接

【MX-X8-T3】「TAOI-3」地地爱打卡 (*1700)

解题思路

真不难吧，只是一个简单分讨，注意到这是一个无向图，因此我们特判以下几种情况：

• 若 $s,t$ 不在一个连通块中，则点 $s$ 一定不能到达点 $t$，输出 expand，这个部分可以简单使用并查集维护。

• 若 $s = t$，且 $s$ 所在的连通块大小为 $1$，且 $x = 0$，则此情况一定合法，不移动即可，输出 tribool。

• 若 $s = t$，且 $s$ 所在的连通块大小为 $1$，且 $x \neq 0$，则此情况一定不合法，因为你无法移动，输出 expand。

此时，特判完这些情况，$s$ 可以到达 $t$，且连通块的大小一定大于 $1$，基于这个性质，我们发现此时点 $s$ 可以无限游走，点 $s$ 能到达 $t$ 且异或和为 $x$ 当前仅当：

• 若 $x$ 为奇数，则 $s$ 到 $t$ 的路程有至少 $1$ 条长度也为奇数。

• 若 $x$ 为偶数，则 $s$ 到 $t$ 的路程有至少 $1$ 条长度也为偶数。

那么我们只需要将这个图黑白染色一下就可以解决了，证明显然，在此不再赘述，时间复杂度为 $O(n \log n + q \log n)$。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define cll const ll
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
ll _t_;
ll n,m,k;
ll x,y,z;
vector<ll>G[1000100];
ll id[1000010];
ll sz[1000010];
ll col[1000010][2];
ll find(ll x)
{
    if(id[x]==x)
        return x;
    return id[x]=find(id[x]);
}
void merge(ll x,ll y)
{
    x=find(x),y=find(y);
    if(x!=y)
    {
        if(sz[x]>sz[y])
            swap(x,y);
        id[x]=y;
        sz[y]+=sz[x];
        sz[x]=0;
    }
}
void Dfs(ll x,ll y)
{
    for(auto i:G[x])
        if(!col[i][y^1])
            col[i][y^1]=1,
            Dfs(i,y^1);
}
void solve()
{
    cin>>n>>m>>k;
    forl(i,1,n)
        sz[i]=1,
        id[i]=i;
    forl(i,1,m)
        cin>>x>>y,
        G[x].pb(y),
        G[y].pb(x),
        merge(x,y);
    forl(i,1,n)
        if(!col[i][0] && !col[i][1])
            col[i][0]=1,
            Dfs(i,0);
    forl(_,1,k)
    {
        cin>>x>>y>>z;
        if(x==y)
        {
            if(z%2)
            {
                if(col[x][0]+col[x][1]==2)
                    cout<<"tribool\n";
                else
                    cout<<"expand\n";
            }
            else if(z && sz[find(x)]==1)
                cout<<"expand\n";
            else
                cout<<"tribool\n";
            continue;
        }
        else if(find(x)!=find(y))
        {
            cout<<"expand\n";
            continue;
        }
        else if(sz[find(x)]==1)
            while(1);
        else if(z%2)
        {
            if(col[x][0]+col[y][1]==2 || col[x][1]+col[y][0]==2)
                cout<<"tribool\n";
            else
                cout<<"expand\n";
        }
        else
        {
            if(col[x][0]+col[y][0]==2 || col[x][1]+col[y][1]==2)
                cout<<"tribool\n";
            else
                cout<<"expand\n";
        }
    }
}
int main()
{
    IOS;
    _t_=1;
    while(_t_--)
        solve();
    QwQ;
}