Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF=2e9;
- using pii = pair<int,int> ;
- int num[50005];
- map <int,int> cnt,mp,amount;
- vector <pii> g[50005];
- bool visited[50005];
- void bfs(int u,int d){
- if(visited[u])
- return ;
- visited[u]=true;
- cnt[num[u]]++;
- for(auto v:g[u]){
- if( v.second>d ) bfs(v.first,d);
- }
- }
- int main(){
- int n,m,k;
- scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i<=n;i++) {
- scanf("%d",&num[i]);
- mp[num[i]]++;
- }
- int l=1,r=INF,mid,ans=0;
- for(int i=1;i<=m;i++){
- int u,v,d;
- scanf("%d%d%d",&u,&v,&d);
- amount[d]++;
- g[u].push_back({v,d});
- g[v].push_back({u,d});
- }
- while(l<=r){
- mid=(l+r)/2;
- bool check=true;
- for(int i=1;i<=n;i++){
- visited[i]=false;
- }
- for(int i=1;i<=n;i++){
- if(!visited[i]){
- bfs(i,mid);
- for(auto j:cnt){
- if(mp[j.first]!=cnt[j.first]){
- check=false;
- break;
- }
- }
- cnt.clear();
- }
- if(!check) break;
- }
- if(check) {
- ans=max(ans,mid);
- l=mid+1;
- }
- else {
- r=mid-1;
- }
- }
- int c=0;
- for(auto i:amount){
- if(i.first<=ans) c+=i.second;
- }
- printf("%d",c);
- return 0;
- }
Add Comment
Please, Sign In to add comment