## Submission #347993

# Submission time Handle Problem Language Result Execution time Memory
347993 2021-01-14T02:43:18 Z arnold518 Swapping Cities (APIO20_swap) C++14
0 / 100
2000 ms 7568 KB
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;

int N, M;

struct Edge
{
int u, v, w;
};
Edge E[MAXM+10];

int deg[MAXN+10], val[MAXN+10], cnt[MAXN+10], sz[MAXN+10];

struct UF
{
int par[MAXN+10];

void init()
{
for(int i=1; i<=N; i++)
{
par[i]=i;
}
}

int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
}uf;

void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W)
{
N=_N; M=_M;
for(int i=0; i<M; i++)
{
int u=_U[i], v=_V[i], w=_W[i];
E[i]={u, v, w};
}
sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
{
return p.w<q.w;
});

}
int getMinimumFuelCapacity(int X, int Y)
{
uf.init();
for(int i=1; i<=N; i++)
{
deg[i]=0;
val[i]=0;
cnt[i]=0;
sz[i]=1;
}
for(int i=1; i<=M; i++)
{
int u=E[i].u, v=E[i].v, w=E[i].w;
deg[u]++; deg[v]++;

int uu=uf.Find(u), vv=uf.Find(v);

if(uu==vv)
{
val[uu]=max(val[uu], deg[u]);
val[uu]=max(val[uu], deg[v]);
cnt[uu]++;
}
else
{
uf.par[vv]=uu;
val[uu]=max(val[uu], val[vv]);
cnt[uu]+=cnt[vv];
sz[uu]+=sz[vv];
val[uu]=max(val[uu], deg[u]);
val[uu]=max(val[uu], deg[v]);
cnt[uu]++;
}

int XX=uf.Find(X), YY=uf.Find(Y);
if(XX!=YY) continue;
if(val[XX]>=3) return w;
if(val[XX]==2 && cnt[XX]==sz[XX]) return w;
}
return -1;
}

#### Subtask #1 0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

#### Subtask #2 0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 2062 ms 7568 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

#### Subtask #4 0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

#### Subtask #5 0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

#### Subtask #6 0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -