Submission #98724

#	Time	Username	Problem	Language	Result	Execution time	Memory
98724		onjo0127	Paths (BOI18_paths)	C++11	100 / 100	1347 ms	23672 KiB

paths

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300009];
int C[300009], D[300009][5];

int main() {
    long long a2 = 0, a3 = 0, a4 = 0, a5 = 0;
    int N, M, K; scanf("%d%d%d",&N,&M,&K);
    for(int i=1; i<=N; i++) {scanf("%d",&C[i]); --C[i];}
    for(int i=0; i<M; i++) {
        int u, v; scanf("%d%d",&u,&v);
        if(C[u] != C[v]) a2 += 2;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1; i<=N; i++) for(auto& it: adj[i]) ++D[i][C[it]];
    for(int i=1; i<=N; i++) {
        for(int a=0; a<5; a++) for(int b=0; b<5; b++) if(a != b && C[i] != a && C[i] != b) a3 += 1LL * D[i][a] * D[i][b];
        for(auto& it: adj[i]) {
            if(C[i] == C[it]) continue;
            for(int a=0; a<5; a++) {
                for(int b=0; b<5; b++) {
                    vector<int> X = {C[i], C[it], a, b};
                  	sort(X.begin(), X.end());
                    if(X[0] != X[1] && X[1] != X[2] && X[2] != X[3]) a4 += 1LL * D[i][a] * D[it][b];
                }
            }
        }
      	if(K == 5) {
          vector<int> S;
          for(int a=0; a<5; a++) if(a != C[i]) S.push_back(a);
          do {
              long long a = 0, b = 0;
              for(auto& it: adj[i]) if(C[it] == S[0]) a += D[it][S[1]];
              for(auto& it: adj[i]) if(C[it] == S[2]) b += D[it][S[3]];
              a4 += a * b;
          } while(next_permutation(S.begin(), S.end()));
        }
    }
    printf("%lld", a2 + a3 + a4 + a5);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M, K; scanf("%d%d%d",&N,&M,&K);
                  ~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=N; i++) {scanf("%d",&C[i]); --C[i];}
                              ~~~~~^~~~~~~~~~~~
paths.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d",&u,&v);
                   ~~~~~^~~~~~~~~~~~~~

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