Submission #394870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394870	2021-04-27T11:47:28 Z	irmuun	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	5808 KB

swap

#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<n;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	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	40 ms	3028 KB	Output is correct
10	Correct	57 ms	3676 KB	Output is correct
11	Correct	62 ms	3632 KB	Output is correct
12	Correct	63 ms	3772 KB	Output is correct
13	Correct	61 ms	3840 KB	Output is correct
14	Execution timed out	2079 ms	3240 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Execution timed out	2075 ms	5808 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 17.0

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

Subtask #4

0 / 20.0

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

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	40 ms	3028 KB	Output is correct
10	Correct	57 ms	3676 KB	Output is correct
11	Correct	62 ms	3632 KB	Output is correct
12	Correct	63 ms	3772 KB	Output is correct
13	Correct	61 ms	3840 KB	Output is correct
14	Execution timed out	2079 ms	3240 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	204 KB	Output isn't correct