# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
927093 |
2024-02-14T09:05:17 Z |
vjudge1 |
Paths (BOI18_paths) |
C++17 |
|
152 ms |
101944 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;
const ll mod=1e9+7;
const ll inf=1e9+7;
const int N=1e6+4;
int n,m,k,a[N],used[N];
ll res=0;
vt<int>g[N][4];
void dfs(int v,int pr){
used[v]=1;
for(int i=1; i<=3; ++i) for(int to:g[v][i]) if(!used[to]) dfs(to,v);
set<int>st;
st.insert(1);
st.insert(2);
st.insert(3);
st.erase(a[v]);
auto bb=st.begin();
auto ee=st.rbegin();
ll aaa=g[v][*ee].size();
ll bbb=g[v][*bb].size();
res+=aaa*bbb;
}
void dfs2(int v,int pr){
used[v]=1;
for(int i=1; i<=3; ++i) for(int to:g[v][i]) if(!used[to]) dfs2(to,v);
set<int>st;
st.insert(1);
st.insert(2);
st.insert(3);
st.erase(a[v]);
auto bb=st.begin();
auto ee=st.rbegin();
//cout<<*bb<<' '<<g[v][*bb].size()<<endl;
ll aaa=g[v][*ee].size();
ll bbb=g[v][*bb].size();
res+=aaa*2ll;
res+=bbb*2ll;
if(pr!=-1 && a[v]!=a[pr]) res-=2ll;
//cout<<v<<' '<<res<<endl;
}
void solve(){
cin>>n>>m>>k;
set<int>uni;
for(int i=1; i<=n; ++i) {
cin>>a[i];
// uni.insert(a[i]);
}
for(int i=1; i<=m; ++i){
int u,v;
cin>>u>>v;
g[u][a[v]].pb(v);
g[v][a[u]].pb(u);
}
if(k==1){
cout<<0<<endl;
return;
}
if(k==2){
for(int i=1; i<=n; ++i) if(!used[i]) dfs2(i,-1);
cout<<res<<endl;
return;
}
if(k==3){
for(int i=1; i<=n; ++i) if(!used[i]) dfs(i,-1);
res*=2ll;
fill(used+1,used+1+n,0);
//cout<<res<<endl;
for(int i=1; i<=n; ++i) if(!used[i]) dfs2(i,-1);
cout<<res<<endl;
}
}
int main(){
int tt=1;
//cin>>tt;
while(tt--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
96856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
152 ms |
101944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
96856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
96860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |