Submission #1111703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111703		PagodePaiva	Paths (BOI18_paths)	C++17	100 / 100	465 ms	122956 KiB

paths

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 300010;
int n,m, k;
vector <int> g[N];
int cor[N];
int res = 0;
int dp[N][6];
int dp2[N][6][6];

void solve(int x){
    if(x == 2){
        int t = 0;
        for(int i = 1;i <= n;i++){
            for(auto x : g[i]){
                if(cor[x] != cor[i]) t++;
            }
        }
        res += t;
        return;
    }
    if(x == 3){
        for(int v = 1;v <= n;v++){
            int resp = 0;
            for(auto x : g[v]){
                if(cor[x] == cor[v]) continue;
                for(int j = 1;j <= k;j++){
                    if(j == cor[x] or j == cor[v]) continue;
                    resp += dp[v][j];
                }
            }
            res += resp;
        }
        return;
    }
    if(x == 4){
        for(int v = 1;v <= n;v++){
            int resp = 0;
            for(auto x : g[v]){
                if(cor[x] == cor[v]) continue;
                for(int j = 1;j <= k;j++){
                    if(cor[x] == j or cor[v] == j) continue;
                    for(int t = 1;t <= k;t++){
                        if(cor[x] == t or cor[v] == t or j == t) continue;
                        resp += dp[v][j]*dp[x][t];
                    }
                }
            }
            res += resp;
        }
    }
    if(x == 5){
        // << res << '\n';
        for(int v = 1;v <= n;v++){
            for(int j = 1;j <= k;j++){
                if(j == cor[v]) continue;
                for(int t = 1;t <= k;t++){
                    if(j == t or t == cor[v])continue;
                    set <int> s;
                    s.insert(1);
                    s.insert(2);
                    s.insert(3);
                    s.insert(4);
                    s.insert(5);
                    s.erase(j);
                    s.erase(t);
                    s.erase(cor[v]);
                    auto it = s.begin();
                    int c1 = *it;
                    it++;
                    int c2 = *it;
                    res += dp2[v][j][t]*(dp2[v][c1][c2] + dp2[v][c2][c1]);
                }
            }
           // cout << res << '\n';
        }
    }
}
int32_t main(){
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++){
        cin >> cor[i];
    }
    for(int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1;i <= n;i++){
        int v = i;
        for(auto x : g[v]){
            dp[v][cor[x]]++;
        }
    }
    for(int i = 1;i <= n;i++){
        int v = i;
        for(auto x : g[v]){
            int c1 = cor[x];
            if(cor[x] == cor[v]) continue;
            for(int j = 1;j <= k;j++){
                if(j == cor[v] or j == c1) continue;
                dp2[v][c1][j] += dp[x][j];
            }
        }
    }
    for(int i = 2;i <= k;i++){
        solve(i);
        //cout << "resposta de i:" << res << '\n';
    }
    cout << res << '\n';
}

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