YEZAELP

CUBE-181: Copying is not permitted

Jul 7th, 2020
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF=1e9;
  4. using pi=pair<int,int>;
  5. int n,m,p;
  6. vector <pi> g[40001];
  7. pi connect[50001];
  8. int color[40001];
  9. void dfs(int u,int c,int d){
  10.     if(color[u]!=0) return ;
  11.     color[u]=c;
  12.     for(auto vw:g[u]){
  13.         int v,w;
  14.         v=vw.first;
  15.         w=vw.second;
  16.         if(color[v]==0 and w<d) dfs(v,c,d);
  17.     }
  18. }
  19. int main(){
  20.     int l=INF,r=-INF,mid;
  21.     scanf("%d %d %d",&n,&m,&p);
  22.     for(int i=1;i<=m;i++){
  23.         int u,v,w;
  24.         scanf("%d %d %d",&u,&v,&w);
  25.         g[u].push_back({v,w});
  26.         g[v].push_back({u,w});
  27.         l=min(l,w);
  28.         r=max(r,w);
  29.     }
  30.  
  31.     int c=1;
  32.     for(int i=1;i<=n;i++){
  33.         if(color[i]==0){
  34.             dfs(i,c,INF);
  35.             c++;
  36.         }
  37.     }
  38.  
  39.     int check=0;
  40.     for(int i=1;i<=p;i++){
  41.         int u,v;
  42.         scanf("%d%d",&u,&v);
  43.         connect[i]={u,v};
  44.         if(color[u]!=color[v]) check++;
  45.     }
  46.     if(check==p){
  47.         printf("-1");
  48.         return 0;
  49.     }
  50.  
  51.     int max_k=0;
  52.     while(l<=r){
  53.         mid=(l+r)/2;
  54.         c=1;
  55.         for(int i=1;i<=n;i++) color[i]=0;
  56.         for(int i=1;i<=n;i++){
  57.             if(color[i]==0){
  58.                 dfs(i,c,mid);
  59.                 c++;
  60.             }
  61.         }
  62.         int cannot_connect=0;
  63.         for(int i=1;i<=p;i++){
  64.             int u,v;
  65.             u=connect[i].first;
  66.             v=connect[i].second;
  67.             if(color[u]!=color[v]) cannot_connect++;
  68.         }
  69.         if(cannot_connect>=p){
  70.             max_k=max(max_k,mid);
  71.             l=mid+1;
  72.         }
  73.         else r=mid-1;
  74.     }
  75.     printf("%d",max_k);
  76.  
  77.     return 0;
  78. }
Add Comment
Please, Sign In to add comment