Submission #986247

#	Time	Username	Problem	Language	Result	Execution time	Memory
986247		Aiperiii	Paths (BOI18_paths)	C++14	100 / 100	436 ms	61996 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],cnt[N][6];
vector <int> g[N][6];
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][cl[v]].pb(v);
        g[v][cl[u]].pb(u);
    }
    int ans=0;
    if(k>=2){
        for(int i=1;i<=n;i++){
            for(int a=1;a<=k;a++){
                if(cl[i]!=a)ans+=g[i][a].size();
            }
        }
    }
    if(k>=3){
        for(int i=1;i<=n;i++){
            for(int a=1;a<=k;a++){
                for(int b=1;b<=k;b++){
                    if(a!=b && a!=cl[i] && b!=cl[i])ans+=g[i][a].size()*g[i][b].size();
                }
            }
        }
    }
    if(k>=4){
        for(int i=1;i<=n;i++){
            for(int b=1;b<=k;b++){
                for(int c=1;c<=k;c++){
                    for(int a=1;a<=k;a++){
                        if(a!=b && a!=cl[i] && b!=cl[i] && c!=b && c!=a && c!=cl[i]){
                            for(auto to : g[i][b])ans+=g[i][a].size()*g[to][c].size();
                        }
                    }
                    
                }
                
            }
        }
    }
    if(k==5){
        for(int i=1;i<=n;i++){
            for(int b=1;b<=k;b++){
                for(int c=1;c<=k;c++){
                    for(int a=1;a<=k;a++){
                        if(a!=b && a!=cl[i] && b!=cl[i] && c!=b && c!=a && c!=cl[i]){
                            int x=0,y=0;
                            int d=15-(cl[i]+a+b+c);
                            for(auto to : g[i][b])x+=g[to][d].size();
                            for(auto to : g[i][a])y+=g[to][c].size();
                            ans+=x*y;
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<"\n";
}

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

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