Submission #1111705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111705		mariaclara	Paths (BOI18_paths)	C++17	100 / 100	310 ms	24380 KiB

paths

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 3e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first 
#define sc second

int n, m, k, c[MAXN];
ll qtd[10];
vector<int> edges[MAXN], color[10];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++)
        cin >> c[i], color[c[i]].pb(i);

    while(m--) {
        int a, b;
        cin >> a >> b;
        edges[a].pb(b);
        edges[b].pb(a);
    }

    vector<int> ord;
    for(int i = 1; i <= k; i++) ord.pb(i);

    do {
        vector<ll> dp(n+1);

        for(int i = 0; i < k; i++) {

            for(auto x : color[ord[i]]) {
                if(!i) { dp[x] = 1; qtd[i]++; continue; }

                for(auto viz : edges[x])
                    if(c[viz] == ord[i-1]) dp[x] += dp[viz];

                qtd[i] += dp[x];
            }

        }
    } while(next_permutation(all(ord)));

    ll ans = 0;

    for(int i = k, fat = 1; i > 1; i--, fat *= (k-i)) 
        ans += qtd[i-1] / fat;

    cout << ans << "\n";
}

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