Submission #1129067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129067		Ludissey	Paths (BOI18_paths)	C++20	100 / 100	333 ms	69596 KiB

paths

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rsz(a,n) a.resize(n)
 
using namespace std;

int n,m,k;
vector<int> c; 
vector<vector<int>> neigh;
vector<vector<int>> memo;

int dfs(int x, int mask){
    if(memo[x][mask]>-1) return memo[x][mask];
    int s=0;
    if(__builtin_popcount(mask)>1) s++;
    for (auto u : neigh[x])
    {
        if(mask&(1<<c[u])) continue;
        s+=dfs(u,mask|(1<<c[u]));
    }
    return memo[x][mask]=s; 
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    rsz(c,n);
    rsz(neigh,n);
    memo.resize(n,vector<int>((1<<k),-1));
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) c[i]--;
    for (int i = 0; i < m; i++){
        int a,b; cin >> a >> b;
        a--; b--;
        neigh[a].push_back(b);
        neigh[b].push_back(a);
    }
    int sm=0;
    for (int i = 0; i < n; i++)
    {
        sm+=dfs(i,(1<<c[i]));
    }
    cout << sm << "\n";
    return 0;
}

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