【題解】Codeforces 1354E. Graph Coloring

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int n, m, l[4], a, b, c[5005], dp[5005][5005], from[5005][5005], ans[5005];
vector <int> v[5005];
vector <vector<int> > cc[2];
 
bool dfs(int x){
    bool ret = true;
    for (auto i:v[x]){
        if (~c[i]){
            if (c[i] == c[x]) return false;
        }
        else{
            c[i] = c[x] ^ 1;
            cc[c[i]].back().push_back(i);
            ret &= dfs(i);
        }
    }
    return ret;
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= 3; i++){
        cin >> l[i];
    }
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(c, -1, sizeof(c));
    for (int i = 1; i <= n; i++){
        if (~c[i]) continue;
        else{
            c[i] = 0;
            cc[0].push_back({i});
            cc[1].push_back({});
            if (!dfs(i)){
                cout << "NO\n";
                return 0;
            }
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < cc[0].size(); i++){
        for (int j = 0; j <= l[2]; j++){
            if (dp[i][j]){
                int tar0 = j+cc[0][i].size();
                if (tar0 <= l[2]){
                    dp[i+1][tar0] = 1;
                    from[i+1][tar0] = 0;
                }
                int tar1 = j+cc[1][i].size();
                if (tar1 <= l[2]){
                    dp[i+1][tar1] = 1;
                    from[i+1][tar1] = 1;
                }
            }
        }
    }
    if (!dp[cc[0].size()][l[2]]){
        cout << "NO\n";
        return 0;
    }
    int ptr = l[2];
    for (int i = cc[0].size(); i > 0; i--){
        int tar = from[i][ptr];
        ptr -= cc[tar][i-1].size();
        for (auto j:cc[tar][i-1]){
            ans[j] = 2;
        }
    }
    for (int i = 1; i <= n; i++){
        if (ans[i]) continue;
        if (l[1]){
            ans[i] = 1;
            l[1]--;
        }
        else ans[i] = 3;
    }
    cout << "YES\n";
    for (int i = 1; i <= n; i++){
        cout << ans[i];
    }
}