Submission #888339

#	Time	Username	Problem	Language	Result	Execution time	Memory
888339		1075508020060209tc	Paths (BOI18_paths)	C++14	70 / 100	783 ms	59400 KiB

paths

#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;
        }
    }

}


}

void solve5(){
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 mid=1;mid<=n;mid++){
    vector<vector<int>>tbl2(6,vector<int>(6,0));
    for(int i=0;i<e[mid].size();i++){
        int nw=e[mid][i];
        if(cr[nw]==cr[mid]){continue;}
        set<int>st;
      //  st.insert(cr[nw]);
        //st.insert(cr[mid]);
        for(int b=1;b<=5;b++){
            for(int x=1;x<=5;x++){
                for(int y=1;y<=5;y++){
                    st.insert(cr[nw]);
                    st.insert(cr[mid]);
                    st.insert(b);
                    st.insert(x);
                    st.insert(y);
                    if(st.size()==5){
                        ans+=tbl[nw][b]*tbl2[x][y];
                    }
                }
            }
        }
        for(int b=1;b<=5;b++){
            tbl2[cr[nw]][b]+=tbl[nw][b];
        }
    }
}



}


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();}
if(K==5){solve5(); }
cout<<ans<<"\n";


}

Compilation message (stderr)

paths.cpp: In function 'void solve3()':
paths.cpp:23:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
paths.cpp: In function 'void solve4()':
paths.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
paths.cpp: In function 'void solve5()':
paths.cpp:65:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
paths.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<e[mid].size();i++){
      |                 ~^~~~~~~~~~~~~~

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