Submission #838528

#	Time	Username	Problem	Language	Result	Execution time	Memory
838528		vjudge1	Paths (BOI18_paths)	C++14	100 / 100	376 ms	97156 KiB

paths

#include <queue>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
vector<int> graph[maxn];
ll dp[maxn][1 << 5];
int color[maxn];
ll dfs(int node, int bitmask, int length) {
    if(dp[node][bitmask] != -1) {
        return dp[node][bitmask];
    }
    ll res = 0;
    if(dp[node][bitmask] != -1) {
        return dp[node][bitmask];
    }
    if(length >= 2) {
        res++;
    }
    for(int neighbour : graph[node]) {
        if(!(bitmask & (1 << color[neighbour]))) {
            res += dfs(neighbour, bitmask | (1 << color[neighbour]), length + 1);
        }
    }
    return dp[node][bitmask] = res;
}
int main(int argc, const char * argv[]) {
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++) {
        cin >> color[i];
        color[i]--;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    memset(dp, -1, sizeof dp);
    ll res = 0;
    for(int i = 0; i < n; i++) {
        res += dfs(i, (1 << color[i]), 1);
    }
    cout << res << endl;
    return 0;
}

//4 3 3 1 2 1 3 1 2
//2 3
//4 2

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