提出 #53129264

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=20,M=66000;
int dp[M][N],n,m,c[N],con[N][N],comp[N],ans[N];
vector<pair<int,int>> adj[N];
vector<int> b,st;
bool vis[M][N];
set<int> valid[N];
void dfs(int x){
    vis[0][x]=1;
    st.pb(x);
    for (auto u:adj[x]){
        if (vis[0][u.F]) continue;
        dfs(u.F);
    }return;
}
void color(int x){
    vis[0][x]=1;
    for (auto u:adj[x]){
        if (vis[0][u.F]) continue;
        c[u.F]=c[x]+u.S;
        color(u.F);
    }return;
}
bool check(int x){
    vis[0][x]=1;
    bool ok=(c[x]>=0 && c[x]<n);
    for (auto u:adj[x]){
        ok&=(c[u.F]==c[x]+u.S);
        if (vis[0][u.F]) continue;
        ok&=check(u.F);
    }return ok;
}
int rec(int mask,int i){
    //cout<<mask<<' '<<i<<endl;
    if (i>=b.size()) return 1;
    if (vis[mask][i]) return dp[mask][i];
    vis[mask][i]=1;
    for (int j=0;j<n;j++){
        if (con[b[i]][j]==-1) continue;
        if (con[b[i]][j]&mask) continue;
        bool x=rec(mask|con[b[i]][j],i+1);
        if (x) valid[b[i]].ep(j);
        dp[mask][i]|=x;
    }return dp[mask][i];
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    memset(con,-1,sizeof(con));
    for (int i=0;i<N;i++) ans[i]=-2;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].pb({y,-z});
        adj[y].pb({x,z});
    }
    for (int i=1;i<=n;i++){
        if (vis[0][i]) continue;
        dfs(i);b.pb(i);
        for (auto u:st) comp[u]=i;
        st.clear();
    }
    for (auto u:b){
        for (int i=0;i<n;i++){
            c[u]=i;
            for (int i=1;i<=n;i++) vis[0][i]=0;
            color(u);
            for (int i=1;i<=n;i++) vis[0][i]=0;
            if (!check(u)) continue;
            int mask=0;
            for (int i=1;i<=n;i++){
                if (comp[i]!=u) continue;
                if (mask&(1<<c[i])){
                    mask=-1;
                    break;
                }
                mask+=(1<<c[i]);
            }
            con[u][i]=mask;
        }
    }
    /*for (auto u:b){
        for (int i=0;i<n;i++){
            if (con[u][i]==-1) cout<<"-1 ";
            else{
                for (int j=0;j<n;j++) cout<<bool(con[u][i]&(1<<j));
                cout<<' ';
            }
        }cout<<endl;
    }*/
    for (int i=1;i<=n;i++) vis[0][i]=0;
    rec(0,0);
    for (auto u:b){
        if (valid[u].size()!=1) continue;
        for (int i=1;i<=n;i++) vis[0][i]=0;
        c[u]=*valid[u].begin();
        color(u);
        for (int i=1;i<=n;i++) if (comp[i]==u) ans[i]=c[i];
    }
    for (int i=1;i<=n;i++) cout<<ans[i]+1<<' ';
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘long long int rec(long long int, long long int)’:
Main.cpp:47:10: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   47 |     if (i>=b.size()) return 1;
      |         ~^~~~~~~~~~

ジャッジ結果