oj.uz

Submission #104782

# Submission time Handle Problem Language Result Execution time Memory
104782 2019-04-09T09:07:33 Z daili Paths (BOI18_paths) C++14
23 / 100
 3000 ms 52156 KB 
#include <bits/stdc++.h>

using namespace std;

long long solve(vector<vector<int>> &adj, int current, int colsUsed, int K, vector<int> &colors, vector<vector<long long>> &dp)
{
    int cnt = 0;

    if (dp[current][colsUsed])
    {
      return dp[current][colsUsed];
    }

    for (auto u : adj[current])
    {
        if ((colsUsed & (1 << colors[u])) == 0)
        {
            cnt += solve(adj, u, colsUsed ^ (1 << colors[u]), K, colors, dp) + 1;
        }
    }
    dp[current][colsUsed] = cnt;
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, K;
    cin >> n >> m >> K;

    vector<int> cols;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        x--;

        cols.push_back(x);
    }

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++)
    {
      int a, b;
      cin >> a >> b;

      a--; b--;
      graph[a].push_back(b);
      graph[b].push_back(a);
    }

    vector<vector<long long>> dp(n+1, vector<long long> (1 << K));

    int res = 0;
    for (int i = 0; i < n; i++)
    {
      res += solve(graph, i, (1 << cols[i]), K, cols, dp);
    }
    cout << res;


    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 4192 KB Output is correct
2 Correct 388 ms 6300 KB Output is correct
3 Correct 620 ms 52156 KB Output is correct
4 Correct 249 ms 10816 KB Output is correct
5 Correct 175 ms 10104 KB Output is correct
6 Execution timed out 3102 ms 37444 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 234 ms 4192 KB Output is correct
12 Correct 388 ms 6300 KB Output is correct
13 Correct 620 ms 52156 KB Output is correct
14 Correct 249 ms 10816 KB Output is correct
15 Correct 175 ms 10104 KB Output is correct
16 Execution timed out 3102 ms 37444 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 127 ms 1520 KB Output isn't correct
3 Halted 0 ms 0 KB -