Submission #852390

#	Time	Username	Problem	Language	Result	Execution time	Memory
852390		Benmath	Paths (BOI18_paths)	C++14	70 / 100	1450 ms	529496 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[300005][6][6][6];
int boja[300005];
int n;
int m;
int k;
vector<int>adjl[300005];
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 node = 1; node <= n; node++){
                    if (i == 0){
                        if (j == 0 and t == 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){
                                    dp[node][i][j][t] += dp[adjl[node][susjed]][boja[node]][0][0];
                                }
                            }
                        }
                    }else{
                        if (j == 0){
                            if (t == 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){
                                         dp[node][i][j][t] += dp[adjl[node][susjed]][i][boja[node]][0];
                                    }
                                  }
                            }
                        }else{
                            if (t == 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){
                                         dp[node][i][j][t] += dp[adjl[node][susjed]][i][j][boja[node]];
                                    }
                               }
                            }else{
                              
                            }
                        }
                    }
                    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(boja[node] != i and boja[node] != j and boja[node] != t and check == 0){
                        dp[node][i][j][t] += 1;
                    }
                    if(i == 0 and j == 0 and t == 0){
                        ans = ans + dp[node][i][j][t];
                        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:37:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                             for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:47:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                                  for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:56:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                                 for (int susjed = 0; susjed < adjl[node].size(); susjed ++){
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~

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