oj.uz

Submission #408704

# Submission time Handle Problem Language Result Execution time Memory
408704 2021-05-19T14:12:57 Z MOUF_MAHMALAT Swapping Cities (APIO20_swap) C++11
13 / 100
 388 ms 41344 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct node
{
    ll u1,u2,w;
} a[200009];
ll n,p[300009],c[100009],ans[300009];
ll dp[300009][20],h[300009],logn;
vector<vector<ll> >v;
bool cmp(const node&xo,const node&yo)
{
    return xo.w<yo.w;
}
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y,ll z)
{
    c[x]++,c[y]++;
    bool is = (c[x]>2||c[y]>2);
    x=gp(x),y=gp(y);
    n++;
    p[x]=p[y]=p[n]=n;
    if(x==y)
    {
        is=1;
        v[n].push_back(x);
    }
    else
    {
        v[n].push_back(x);
        v[n].push_back(y);
    }
    if(is)
        ans[n]=z;
    else
        ans[n]=2e9;
}
void dfs(ll d,ll pp)
{
    dp[d][0]=pp;
    h[d]=h[pp]+1;
    ans[d]=min(ans[d],ans[pp]);
    for(auto z:v[d])
        dfs(z,d);
    if(ans[d]==2e9)
        ans[d]=-1;
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
    v.resize(N+M+9);
    for(ll i=0; i<M; i++)
    {
        a[i].u1=U[i];
        a[i].u2=V[i];
        a[i].w =W[i];
    }
    sort(a,a+M,cmp);
    n=N-1;
    for(ll i=0; i<N; i++)
        p[i]=i,ans[i]=2e9;
    for(ll i=0; i<M; i++)
        mrg(a[i].u1,a[i].u2,a[i].w);
    logn=log2(n)+1;
    ll root=gp(0);
    dfs(root,root);
    for(ll j=1; j<=logn; j++)
        for(ll i=0; i<=n; i++)
            dp[i][j]=dp[ dp[i][j-1] ][j-1];
}
int getMinimumFuelCapacity(int x, int y)
{
    ll lca;
    if(h[x]<h[y])
        swap(x,y);
    ll dif=h[x]-h[y];
    for(ll i=logn; i>=0; i--)
        if(dif&(1<<i))
            x=dp[x][i];
    for(ll i=logn; i>=0; i--)
        if(dp[x][i]!=dp[y][i])
            x=dp[x][i],y=dp[y][i];
    if(x==y)
        lca=x;
    else
        lca=dp[x][0];
    return ans[lca];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 100 ms 23620 KB Output is correct
10 Correct 132 ms 28880 KB Output is correct
11 Correct 144 ms 28420 KB Output is correct
12 Correct 132 ms 30048 KB Output is correct
13 Correct 126 ms 32416 KB Output is correct
14 Correct 116 ms 23764 KB Output is correct
15 Correct 265 ms 30892 KB Output is correct
16 Correct 266 ms 30052 KB Output is correct
17 Correct 282 ms 31756 KB Output is correct
18 Correct 388 ms 34100 KB Output is correct
19 Correct 96 ms 8388 KB Output is correct
20 Correct 267 ms 36304 KB Output is correct
21 Correct 267 ms 35456 KB Output is correct
22 Correct 267 ms 37584 KB Output is correct
23 Correct 351 ms 39944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 322 ms 35824 KB Output is correct
4 Correct 322 ms 41344 KB Output is correct
5 Correct 325 ms 40532 KB Output is correct
6 Correct 304 ms 41272 KB Output is correct
7 Correct 312 ms 41008 KB Output is correct
8 Correct 299 ms 39456 KB Output is correct
9 Correct 289 ms 40644 KB Output is correct
10 Correct 339 ms 39196 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Incorrect 1 ms 588 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 100 ms 23620 KB Output is correct
11 Correct 132 ms 28880 KB Output is correct
12 Correct 144 ms 28420 KB Output is correct
13 Correct 132 ms 30048 KB Output is correct
14 Correct 126 ms 32416 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Incorrect 1 ms 588 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 100 ms 23620 KB Output is correct
10 Correct 132 ms 28880 KB Output is correct
11 Correct 144 ms 28420 KB Output is correct
12 Correct 132 ms 30048 KB Output is correct
13 Correct 126 ms 32416 KB Output is correct
14 Correct 116 ms 23764 KB Output is correct
15 Correct 265 ms 30892 KB Output is correct
16 Correct 266 ms 30052 KB Output is correct
17 Correct 282 ms 31756 KB Output is correct
18 Correct 388 ms 34100 KB Output is correct
19 Correct 322 ms 35824 KB Output is correct
20 Correct 322 ms 41344 KB Output is correct
21 Correct 325 ms 40532 KB Output is correct
22 Correct 304 ms 41272 KB Output is correct
23 Correct 312 ms 41008 KB Output is correct
24 Correct 299 ms 39456 KB Output is correct
25 Correct 289 ms 40644 KB Output is correct
26 Correct 339 ms 39196 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Incorrect 1 ms 588 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 100 ms 23620 KB Output is correct
11 Correct 132 ms 28880 KB Output is correct
12 Correct 144 ms 28420 KB Output is correct
13 Correct 132 ms 30048 KB Output is correct
14 Correct 126 ms 32416 KB Output is correct
15 Correct 116 ms 23764 KB Output is correct
16 Correct 265 ms 30892 KB Output is correct
17 Correct 266 ms 30052 KB Output is correct
18 Correct 282 ms 31756 KB Output is correct
19 Correct 388 ms 34100 KB Output is correct
20 Correct 322 ms 35824 KB Output is correct
21 Correct 322 ms 41344 KB Output is correct
22 Correct 325 ms 40532 KB Output is correct
23 Correct 304 ms 41272 KB Output is correct
24 Correct 312 ms 41008 KB Output is correct
25 Correct 299 ms 39456 KB Output is correct
26 Correct 289 ms 40644 KB Output is correct
27 Correct 339 ms 39196 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Incorrect 1 ms 588 KB Output isn't correct
30 Halted 0 ms 0 KB -