oj.uz

Submission #395224

# Submission time Handle Problem Language Result Execution time Memory
395224 2021-04-28T03:11:26 Z irmuun Swapping Cities (APIO20_swap) C++17
0 / 100
 1 ms 332 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,i,n,m,link[200000],edge[200000],sz[200000],x,y,ans[200000],edgeNum[200000],h[200000],d,e;
pair<int, pair<int,int> >p[200000];
int find(int x){
  if(link[x]==x){
    return x;
  }
  return link[x]=find(link[x]);
}
bool same(int a,int b){
  if(find(a)==find(b)){
    return true;
  }
  else{
    return false;
  }
}
void unite(int a,int b){
  a=find(a);
  b=find(b);
  if(sz[a]<sz[b]){
    swap(a,b);
  }
  if(ans[b]==1){
    ans[a]=1;
  }
  link[b]=a;
  sz[a]+=sz[b];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  m=M;
  n=N;
  for(i=0;i<M;i++){
    p[i].first=W[i];
    p[i].second.first=U[i];
    p[i].second.second=V[i];
    edgeNum[U[i]]++;
    edgeNum[V[i]]++;
  }
  sort(p,p+m);
  for(i=0;i<n;i++){
    h[edgeNum[i]]++;
  }
}
int getMinimumFuelCapacity(int X, int Y) {
  if(h[2]==n){
    return p[m-1].first;
  }
  if(h[1]==n-1){
    for(i=0;i<m;i++){
      if(p[i].second.second==X){
        d=p[i].first;
      }
      if(p[i].second.second==Y){
        e=p[i].first;
      }
    }
    return max(p[2].first,max(d,e));
  }
  for(i=0;i<n;i++){
    link[i]=i;
    sz[i]=1;
    edge[i]=0;
    ans[i]=0;
  }
  for(i=0;i<m;i++){
    x=p[i].second.first;
    y=p[i].second.second;
    edge[x]++;
    edge[y]++;
    if(find(x)==find(y)||edge[x]>2||edge[y]>2){
      ans[find(x)]=1;
      ans[find(y)]=1;
    }
    unite(x,y);
    if(find(X)==find(Y)&&ans[find(X)]==1){
      return p[i].first;
    }
  }
  return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct