Submission #151150

#	Time	Username	Problem	Language	Result	Execution time	Memory
151150		Blagojce	Paths (BOI18_paths)	C++11	100 / 100	821 ms	60844 KiB

paths

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;

int n, m, k;
int col[300005];
vector<int> g[300005];
int dp[300005][33];
void input(){
        memset(dp, -1, sizeof(dp));
        cin >> n >> m >> k;
        fr(i, 0, n){
                cin >> col[i];
                --col[i];
        }
        fr(i, 0, m){
                int a, b;
                cin >> a >> b;
                --a,--b;
                g[a].pb(b);
                g[b].pb(a);
        }
}
ll dfs(int u, int bit){
        if(dp[u][bit] != -1) return dp[u][bit];
        ll cnt = 0;
        for(auto e : g[u]){
                if((bit&(1 << col[e])) == 0){
                        cnt += dfs(e,(bit|(1<<col[e]))) + 1;
                }
        }
        dp[u][bit] = cnt;
        return cnt;
}
void solve(){
        ll ANS = 0;
        fr(i, 0, n){
                ANS += dfs(i, (1 << col[i]));
        }
        cout << ANS << endl;
}


int main()
{
        input();
        solve();
        return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30