Submission #1090322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090322		andrei_iorgulescu	Paths (BOI18_paths)	C++14	100 / 100	750 ms	41556 KiB

paths

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, m, k;
int a[300005];
vector<int> g[300005];
int ans;
bool iau[10];
int dp[300005][7];

void solve(vector<int> mele)
{
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        if (a[i] == mele[0])
            dp[i][1] = 1;
    for (int j = 2; j <= mele.size(); j++)
    {
        for (int i = 1; i <= n; i++)
            if (a[i] == mele[j - 1])
                for (auto vecin : g[i])
                    dp[i][j] += dp[vecin][j - 1];
    }
    for (int i = 1; i <= n; i++)
        ans += dp[i][mele.size()];
}

void bkt(int pos)
{
    if (pos == k + 1)
    {
        vector<int> mele;
        for (int i = 1; i <= k; i++)
            if (iau[i])
                mele.push_back(i);
        if (mele.empty())
            return;
        do
        {
            solve(mele);
        }while (next_permutation(mele.begin(), mele.end()));
    }
    else
    {
        iau[pos] = false;
        bkt(pos + 1);
        iau[pos] = true;
        bkt(pos + 1);
    }
}

signed main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bkt(1);
    cout << ans - n;
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'void solve(std::vector<long long int>)':
paths.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 2; j <= mele.size(); j++)
      |                     ~~^~~~~~~~~~~~~~

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