Submission #96540

#	Time	Username	Problem	Language	Result	Execution time	Memory
96540		Kastanda	Paths (BOI18_paths)	C++11	100 / 100	795 ms	32664 KiB

paths

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 300005;
int n, m, k, C[N];
long long tot, dp[N];
vector < int > P, A[N], Adj[N];
inline void Solve()
{
    if ((int)P.size() <= 1)
        return ;
    vector < int > V = P;
    do
    {
        memset(dp, 0, sizeof(dp));
        for (int v : A[V[0]])
            dp[v] = 1;
        for (int i = 1; i < (int)V.size(); i++)
            for (int v : A[V[i]])
                for (int u : Adj[v])
                    if (C[u] == V[i - 1])
                        dp[v] += dp[u];
        for (int v : A[V.back()])
            tot += dp[v];
    } while (next_permutation(V.begin(), V.end()));
}
void Generate(int a)
{
    if ((int)P.size() == k || a > k)
        return ;
    P.pb(a); Solve();
    Generate(a + 1);
    P.pop_back();
    Generate(a + 1);
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &C[i]), A[C[i]].pb(i);
    for (int i = 1; i <= m; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[v].pb(u);
        Adj[u].pb(v);
    }
    Generate(1);
    return !printf("%lld\n", tot);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:38: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:40:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C[i]), A[C[i]].pb(i);
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
paths.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~

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