Submission #1219780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219780		4QT0R	Paths (BOI18_paths)	C++20	100 / 100	455 ms	92832 KiB

paths

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int kol[300002];
vector<int> graph[300002];
ll dp[300002][32];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m,k;
    cin >> n >> m >> k;
    for (int i = 1; i<=n; i++){
        cin >> kol[i];
        kol[i]--;
        dp[i][1<<kol[i]]=1;
    }
    for (int i = 1,a,b; i<=m; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    ll ans=0;
    for (int i = 1; i<31; i++){
        for (int v = 1; v<=n; v++){
            for (auto u : graph[v]){
                int x = i|(1<<kol[u]);
                if (x!=i){
                    ans+=dp[v][i];
                    dp[u][x]+=dp[v][i];
                }
            }
        }
    }
    cout << ans << '\n';
}

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