Submission #888335

#TimeUsernameProblemLanguageResultExecution timeMemory
8883351075508020060209tcPaths (BOI18_paths)C++14
0 / 100
122 ms28304 KiB
#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)

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++){
      |                 ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...