oj.uz

Submission #394897

# Submission time Handle Problem Language Result Execution time Memory
394897 2021-04-27T12:44:47 Z irmuun Swapping Cities (APIO20_swap) C++17
0 / 100
 363 ms 524292 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];
pair<int, pair<int,int> >p[200000];
int find(int x){
  if(link[x]==x){
    return x;
  }
  return link[x]=find(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=V[i];
    p[i].second.second=U[i];
  }
  sort(p,p+m);
}
int getMinimumFuelCapacity(int X, int Y) {
  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 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -