Submission #852391

#	Time	Username	Problem	Language	Result	Execution time	Memory
852391		Benmath	Paths (BOI18_paths)	C++14	23 / 100	3137 ms	968848 KiB

paths

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;
long long int dp[100005][6][6][6][6];
int boja[100005];
int n;
int m;
int k;
vector<int>adjl[100005];
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++){
        cin >> boja[i];
    }
    for (int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        adjl[x].push_back(y);
        adjl[y].push_back(x);
    }
    long long int ans = 0;
    for (int i = k; i >= 0; i--){
        for (int j = k; j >= 0; j--){
            for (int t = k; t >= 0; t--){
                for (int t1 = k; t1 >= 0; t1--){
                    for (int node = 1; node <= n; node++){
                       if (i == 0){
                         if (j == 0 and t == 0 and t1 == 0){
                            for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
                                int x = boja[adjl[node][susjed]];
                                if(x != boja[node] and x != i and x != j and x != t and x != t1){
                                    dp[node][i][j][t][t1] += dp[adjl[node][susjed]][boja[node]][0][0][0];
                                }
                            }
                        }
                    }else{
                        if (j == 0){
                            if (t == 0 and t1 == 0){
                                 for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
                                    int x = boja[adjl[node][susjed]];
                                    if(x != boja[node] and x != i and x != j and x != t and x!=t1){
                                         dp[node][i][j][t][t1] += dp[adjl[node][susjed]][i][boja[node]][0][0];
                                    }
                                  }
                            }
                        }else{
                            if (t == 0){
                                if(t1==0){
                                for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
                                    int x = boja[adjl[node][susjed]];
                                    if(x != boja[node] and x != i and x != j and x != t and x!=t1){
                                         dp[node][i][j][t][t1] += dp[adjl[node][susjed]][i][j][boja[node]][0];
                                    }
                               }
                                }
                            }else{
                              for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
                                    int x = boja[adjl[node][susjed]];
                                    if(x != boja[node] and x != i and x != j and x != t and x!=t1){
                                         dp[node][i][j][t][t1] += dp[adjl[node][susjed]][i][j][t][boja[node]];
                                    }
                               }
                            }
                        }
                    }
                    int check = 0;
                    if (i == j and i > 0){
                        check ++;
                    } 
                    if (j == t and j > 0){
                        check ++;
                    }
                    if (i == t and i > 0){
                        check ++;
                    }
                    if (i == t1 and i > 0){
                        check ++;
                    }
                    if(j==t1 and j>0){
                        check++;
                    }
                    if(t==t1 and t>0){
                        check++;
                    }
                    if(boja[node] != i and boja[node] != j and boja[node] != t and check == 0 and boja[node] != t1){
                        dp[node][i][j][t][t1] += 1;
                    }
                    if(i == 0 and j == 0 and t == 0 and t1==0){
                        ans = ans + dp[node][i][j][t][t1];
                        ans --;
                    }
                    //cout << dp[node][i][j][t]<<" "<<i<<" "<<j<<" "<<t<<" "<<node<<" "<<boja[node]<<endl;
                }
            }
        }
    }
    }
    cout << ans << endl;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:38:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                             for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:48:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                                  for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:58:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                                 for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:66:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                               for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~

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