oj.uz

Submission #394868

# Submission time Handle Problem Language Result Execution time Memory
394868 2021-04-27T11:45:07 Z irmuun Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 5884 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,i,n,m,par[100000],edge[100000],sz[100000];
bool ans[100000];
pair<int, pair<int,int> >p[200000];
int find(int x){
  while(x!=par[x]){
    x=par[x];
  }
  return x;
}
bool connect(int a,int b){
  if(find(a)==find(b)){
    return true;
  }
  else{
    return false;
  }
}
void unite(int a,int b){
  edge[a]++;
  edge[b]++;
  a=find(a);
  b=find(b);
  if(sz[a]<sz[b]){
    swap(a,b);
  }
  if(edge[a]==3||edge[b]==3||ans[b]==true){
    ans[a]=true;
  }
  par[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<100000;i++){
    par[i]=i;
    sz[i]=1;
    edge[i]=0;
  }
  for(i=0;i<m;i++){
    unite(p[i].second.first,p[i].second.second);
    if(connect(X,Y)==true){
      if(ans[find(X)]==true||ans[find(Y)]==true){
        return p[i].first;
      }
    }
  }
  return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1468 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 42 ms 3932 KB Output is correct
10 Correct 75 ms 4576 KB Output is correct
11 Correct 76 ms 4712 KB Output is correct
12 Correct 76 ms 4848 KB Output is correct
13 Correct 60 ms 4812 KB Output is correct
14 Execution timed out 2057 ms 4124 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Execution timed out 2072 ms 5884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1468 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Incorrect 1 ms 1484 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1468 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 42 ms 3932 KB Output is correct
10 Correct 75 ms 4576 KB Output is correct
11 Correct 76 ms 4712 KB Output is correct
12 Correct 76 ms 4848 KB Output is correct
13 Correct 60 ms 4812 KB Output is correct
14 Execution timed out 2057 ms 4124 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct