Submission #171259

#	Time	Username	Problem	Language	Result	Execution time	Memory
171259		mehrdad_sohrabi	Railway (BOI17_railway)	C++14	0 / 100	138 ms	20252 KiB

railway

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=3e5+100,M=5;
ll dp[N][(1<<M)];
vector <int> g[N];
ll r[N];
int32_t main(){
    ll n,m,k;
    cin >> n >> m >> k;
    for (int i=1;i<=n;i++){
        cin >> r[i];
        r[i]--;
    }
    for (int i=0;i<m;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (int i=1;i<(1<<k);i++){
        vector <int> bit;
        ll e=i;
        ll o=i;
        ll t1=0;
        while(e){
            bit.pb(e%2);
            if (e%2) t1++;
            e/=2;
        }
        if (t1==1){
            for (int j=1;j<=n;j++){
                if (bit[r[j]]==1){
                    dp[j][o]=1;
                }
            }
            continue;
        }
        while(bit.size()<k) bit.pb(0);
        for (int j=1;j<=n;j++){
            if (bit[r[j]]==0) continue;
            for (int l=0;l<g[j].size();l++){
                ll v=g[j][l];
                dp[j][o]+=dp[v][(o^(1<<r[j]))];
            }

           // cout << " " << j << " " << dp[j][o] << endl;
        }

    }
    ll ans=0;
    for (int i=1;i<(1<<k);i++){
        if (__builtin_popcount(i)>1){
            for (int j=1;j<=n;j++){
                ans+=dp[j][i];
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:51:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(bit.size()<k) bit.pb(0);
               ~~~~~~~~~~^~
railway.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l=0;l<g[j].size();l++){
                          ~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25