Submission #986234

#	Time	Username	Problem	Language	Result	Execution time	Memory
986234		Aiperiii	Paths (BOI18_paths)	C++14	20 / 100	255 ms	25176 KiB

paths

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
int cl[N];
vector <int> g[N];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>cl[i];
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int ans=0;
    if(k>=2){
        for(int i=1;i<=n;i++){
            for(auto to : g[i]){
                if(cl[i]!=cl[to])ans++;
            }
        }
    }
    if(k>=3){
        for(int i=1;i<=n;i++){
            vector <int> cnt(k+1);
            for(auto to : g[i]){
                cnt[cl[to]]++;
            }
            for(int a=1;a<=k;a++){
                for(int b=1;b<=k;b++){
                    if(a!=b && a!=cl[i] && b!=cl[i])ans+=cnt[a]*cnt[b];
                }
            }
        }
    }
    cout<<ans<<"\n";
}

/*
4 3 3
1 2 1 3
1 2
2 3
4 2
 
 
9 11 1
1 1 1 1 1 1 1 1 1
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8
*/

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