# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
888336 | 1075508020060209tc | Paths (BOI18_paths) | C++14 | 364 ms | 64184 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//const int mod=998244353;
int n;int m;int K;
int cr[500005];
int ar[500005];
int br[500005];
vector<int>e[500005];
int ans;
void solve2(){
for(int i=1;i<=m;i++){
if(cr[ar[i]]!=cr[br[i]]){ans+=2;}
}
}
void solve3(){
int ret=0;
for(int nw=1;nw<=n;nw++){
vector<int>tbl(10,0);
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i];
for(int j=1;j<=5;j++){
if(j==cr[v]){continue;}
if(j==cr[nw]){continue;}
if(cr[v]==cr[nw]){continue;}
ret+=tbl[j];
}
tbl[cr[v]]++;
}
}
ret*=2;
ans+=ret;
}
void solve4(){
vector<vector<int>>tbl(n+10,vector<int>(6,0));
for(int nw=1;nw<=n;nw++){
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i];
if(cr[v]!=cr[nw]){
tbl[nw][cr[v]]++;
}
}
}
for(int i=1;i<=m;i++){
int a=ar[i];int b=br[i];
for(int x=1;x<=5;x++){
for(int y=1;y<=5;y++){
if(x==cr[a]||y==cr[a]||x==cr[b]||y==cr[b]||x==y||cr[a]==cr[b]){continue;}
ans+=tbl[a][x]*tbl[b][y]*2;
}
}
}
}
signed main(){
cin>>n>>m>>K;
for(int i=1;i<=n;i++){
cin>>cr[i];
}
for(int i=1;i<=m;i++){
cin>>ar[i]>>br[i];
e[ar[i]].push_back(br[i]);
e[br[i]].push_back(ar[i]);
}
ans=0;
solve2();
solve3();
//cout<<ans<<" ";
if(K>=4){solve4();}
cout<<ans<<"\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |