题解：P11337 [COI 2019] IZLET

· · 题解

[COI 2019] IZLET 题解

博客园：[COI 2019] IZLET 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

构造，并查集。

分析

Sub 1

将 1 的边缩点，此时所有相连的点对颜色互不相同，那么连接就很容易。

可以考虑找一个点作为 1，其余都是 2，并与它相连。

Sub 2

考虑往回找颜色相同的点，其实比较简单。假设从 1 到 n 确定颜色，此时到了 r，那么 1\sim r-1 的颜色都已确定。

从 r-1 往回遍历，现在在 l，如果有 a_{l,r}=a_{l,r-1}，就说明 l 与 r 颜色相同，直接退出即可。

如果没有这样的点，那么重新开一个颜色即可。

Sub 3

考虑满分做法。其实上面两个子任务，一个是教你如何连边，另一个是教你如何染色，所以稍加改动即可得到正解。

连边

首先将 1 的边缩点，然后把 2 的边连起来作为树边，为了结构合法，我们需要用并查集来放置重复连接。

染色

考虑从每个点开始遍历，像 Sub 2 一样，不过这次是在树上，那么我们考虑当找到与 u 一个颜色相同的点，那么我们用最近子节点 son 代替 r-1，判断 a_{v,u}=a_{v,son} 即可，找到之后仍然是立即回溯，由于不能直接确定颜色，这里再用一个并查集连起来。

那么最后每种存在的颜色都会把整个树跑一遍，保证了解的正确性，复杂度也就是均摊 O(n^2)。

代码

constexpr int N(3e3+10);

int ID,n;
int col[N];
int a[N][N];
struct DSU {
    int fa[N];

    int operator [](int x) {
        return Get(x);
    }

    void Init(int n) {
        FOR(i,1,n)fa[i]=i;
    }

    int Get(int x) {
        return fa[x]^x?fa[x]=Get(fa[x]):x;
    }

    bool Merge(int u,int v) {
        if((u=Get(u))==(v=Get(v)))return 0;
        return fa[u]=v,1;
    }

} ;

namespace Subtask1 {
    int idx;
    vector<int> vec[N];
    DSU dsu;

    bool Check() {
        return ID==1;
    }

    int Cmain() {
        dsu.Init(n);
        FOR(i,1,n)FOR(j,i+1,n)if(a[i][j]==1)dsu.Merge(i,j);
        FOR(i,1,n)vec[dsu.Get(i)].push_back(i);
        FOR(i,1,n)if(!vec[i].empty())idx=i;
        /*Output*/
        FOR(i,1,n)O(dsu.Get(i)==idx?1:2," \n"[i==n]);
        FOR(i,1,n)if(i!=idx&&!vec[i].empty())O(vec[idx].front(),' ',vec[i].front(),'\n');
        FOR(i,1,n)FOR(j,0,vec[i].size()-2)O(vec[i][j],' ',vec[i][j+1],'\n');
        return 0;
    }

}

namespace Subtask2 {

    bool Check() {
        return ID==2;
    }

    int Cmain() {
        col[1]=1;
        FOR(r,2,n) {
            DOR(l,r-1,1)if(a[l][r]==a[l][r-1]&&a[l+1][r]==a[l][r]) {
                col[r]=col[l];
                break;
            }
            if(!col[r])col[r]=r;
        }
        FOR(i,1,n)O(col[i]," \n"[i==n]);
        FOR(i,1,n-1)O(i,' ',i+1,'\n');
        return 0;
    }

}

namespace Subtask {
    vector<int> g[N];
    vector<pair<int,int> > Ans;
    DSU D[3];

    void dfs(int u,int fa,int son,int rt) {
        if(son!=u&&a[u][son]!=a[fa][son]&&a[fa][rt]!=a[fa][son]&&a[u][son]==a[u][rt])D[2].Merge(u,rt);
        for(int v:g[u])if(v^fa)dfs(v,u,son,rt);
    }

    int Cmain() {
        D[0].Init(n),D[1].Init(n),D[2].Init(n);
        FOR(i,1,n)FOR(j,i+1,n)if(a[i][j]==1)D[0].Merge(i,j);
        FOR(i,1,n)if(D[0][i]==i)FOR(j,i+1,n)if(D[0][j]==j&&a[i][j]==2&&D[1].Merge(i,j))
            g[i].push_back(j),g[j].push_back(i),Ans.push_back({i,j});
        FOR(u,1,n)if(D[0][u]==u)for(int v:g[u])dfs(v,u,v,u);
        FOR(i,1,n)col[i]=i;
        FOR(i,1,n)if(D[0][i]==i)col[i]=col[D[2][i]];
        FOR(i,1,n)if(D[0][i]^i)col[i]=col[D[0][i]],Ans.push_back({i,D[0][i]});
        FOR(i,1,n)O(col[i]," \n"[i==n]);
        for(pair<int,int> x:Ans)O(x.first,' ',x.second,'\n');
        return 0;
    }

}

int main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    /*Input*/
    I(ID,n);
    FOR(i,1,n)FOR(j,1,n)I(a[i][j]);
    /*Subtasks*/
    if(Subtask1::Check())return Subtask1::Cmain();
    if(Subtask2::Check())return Subtask2::Cmain();
    return Subtask::Cmain();
}