Submission #148109

#	Time	Username	Problem	Language	Result	Execution time	Memory
148109		WhipppedCream	Paths (BOI18_paths)	C++17	100 / 100	481 ms	60924 KiB

paths

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 3e5+5;
int dp[maxn][33];
vi adj[maxn];
int col[maxn];
int ways(int u, int bit)
{
    ll res = 1;
    if(dp[u][bit] != -1) return dp[u][bit];
    for(auto v : adj[u])
    {
        if((1<<col[v]) & bit) continue;
        res += ways(v, bit | (1<<col[v]));
    }
    return dp[u][bit] = res;
}
int main()
{
    memset(dp, -1, sizeof dp);
    int n, m, k; scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i<= n; i++) scanf("%d", col+i);
    for(int i = 1; i<= n; i++) col[i]--;
    while(m--)
    {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].pb(v); adj[v].pb(u);
    }
    ll ret = 0;
    for(int i = 1; i<= n; i++) ret += ways(i, 1<<col[i]);
    printf("%lld\n", ret-n);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:27:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m, k; scanf("%d %d %d", &n, &m, &k);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:28:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i<= n; i++) scanf("%d", col+i);
                                ~~~~~^~~~~~~~~~~~~
paths.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~

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