Submission #231322

#	Time	Username	Problem	Language	Result	Execution time	Memory
231322		DodgeBallMan	Paths (BOI18_paths)	C++14	100 / 100	440 ms	116056 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int n, m, k, col[N];
long long dp[N][40], ans;
vector<int> g[N];

long long solve( int u, int bit ) {
    long long &ret = dp[u][bit];
    if( ret != -1 ) return ret;
    ret = 1;
    for( int v : g[u] ) if( ( 1<<col[v] ) & bit ) ret += solve( v, bit - ( 1<<col[v] ) );
    return ret;
}

int main()
{
    memset( dp, -1, sizeof dp );
    scanf("%d %d %d",&n,&m,&k);
    for( int i = 1 ; i <= n ; i++ ) {
        scanf("%d",&col[i]);
        col[i]--;
    }
    for( int i = 1, a, b ; i <= m ; i++ ) {
        scanf("%d %d",&a,&b);
        g[a].emplace_back( b ), g[b].emplace_back( a );
    }
    for( int i = 1 ; i <= n ; i++ ) ans += solve( i, (1<<k)-(1<<col[i])-1 ) - 1;
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&col[i]);
         ~~~~~^~~~~~~~~~~~~~
paths.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

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