Submission #98722

#	Time	Username	Problem	Language	Result	Execution time	Memory
98722		onjo0127	Paths (BOI18_paths)	C++11	73 / 100	3042 ms	28152 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++) {
                    set<int> st = {C[i], C[it], a, b};
                    if((int)st.size() == 4) a4 += 1LL * D[i][a] * D[it][b];
                }
            }
        }
        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: 0 / 27
• Subtask 4: 30 / 30