Submission #869372

#	Time	Username	Problem	Language	Result	Execution time	Memory
869372		12345678	Paths (BOI18_paths)	C++17	23 / 100	3069 ms	13980 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;
int n, m, k, u, v, c[nx];
vector<int> d[nx];
long long ans;

void dfs(int u, int s)
{
    ans++;
    for (auto v:d[u]) if (!(s&(1<<c[v]))) dfs(v, s+(1<<c[v]));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<=n; i++) cin>>c[i];
    for (int i=0; i<m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) dfs(i, 1<<c[i]);
    cout<<ans-n;
}

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