oj.uz

Submission #171259

# Submission time Handle Problem Language Result Execution time Memory
171259 2019-12-28T06:17:33 Z mehrdad_sohrabi Railway (BOI17_railway) C++14
0 / 100
 138 ms 20252 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 19492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 20252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 20252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -