Submission #933270

#	Time	Username	Problem	Language	Result	Execution time	Memory
933270		LucaIlie	Paths (BOI18_paths)	C++17	100 / 100	728 ms	25684 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5;
const int MAX_K = 5;
int color[MAX_N + 1];
int vis[MAX_K + 1];
long long dp[MAX_N + 1];
vector<int> perm;
vector<vector<int>> perms;
vector<int> adj[MAX_N + 1], verticesByColor[MAX_K + 1];

void genAranj( int i, int n, int k ) {
    if ( i == k ) {
        perms.push_back( perm );
        return;
    }

    for ( int x = 1; x <= n; x++ ) {
        if ( vis[x] )
            continue;

        perm.push_back( x );
        vis[x] = true;
        genAranj( i + 1, n, k );
        vis[x] = false;
        perm.pop_back();
    }
}

int main() {
    int n, m, k;

    cin >> n >> m >> k;
    for ( int v = 1; v <= n; v++ ) {
        cin >> color[v];
        verticesByColor[color[v]].push_back( v );
    }
    for ( int i = 0; i < m; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    for ( int i = 2; i <= k; i++ )
        genAranj( 0, k, i );

    long long ans = 0;
    for ( vector<int> perm: perms ) {
        for ( int v = 1; v <= n; v++ )
            dp[v] = (color[v] == perm[0] ? 1 : 0);

        for ( int i = 1; i < perm.size(); i++ ) {
            for ( int u: verticesByColor[perm[i]] ) {
                for ( int v: adj[u] ) {
                    if ( color[v] == perm[i - 1])
                        dp[u] += dp[v];
                }
            }
        }

        for ( int v = 1; v <= n; v++ )
            ans = ans + (color[v] == perm[perm.size() - 1] ? dp[v] : 0);
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:55:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for ( int i = 1; i < perm.size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~

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