oj.uz

Submission #1055190

# Submission time Handle Problem Language Result Execution time Memory
1055190 2024-08-12T15:14:03 Z alexander707070 Swapping Cities (APIO20_swap) C++17
7 / 100
 110 ms 26188 KB 
#include<bits/stdc++.h>
#include "swap.h"

#define MAXN 100007
using namespace std;

int n,m;

struct edge{
    int from,to,cost;
    
    inline friend bool operator < (edge fr,edge sc){
        return fr.cost<sc.cost;
    }
}e[MAXN];

int closest[MAXN],special[MAXN];
int lt[MAXN],rt[MAXN];
vector<int> query[MAXN];

struct union_find{
    int dsu[MAXN],sz[MAXN],trip[MAXN],deg[MAXN];

    void reset(){
        for(int i=1;i<=n;i++){
            dsu[i]=i; sz[i]=1; trip[i]=deg[i]=0;
        }
    }

    int root(int x){
        if(dsu[x]==x)return dsu[x];
        dsu[x]=root(dsu[x]);
        return dsu[x];
    }

    void mergev(int x,int y){
        int rootx=root(x);
        int rooty=root(y);

        deg[x]++; deg[y]++;

        if(deg[x]>=3)trip[rootx]=x;
        if(deg[y]>=3)trip[rootx]=y;

        if(rootx==rooty)return;
        if(sz[rootx]<sz[rooty])swap(rootx,rooty);

        dsu[rooty]=rootx;
        sz[rootx]+=sz[rooty];
        if(trip[rooty]!=0)trip[rootx]=trip[rooty];
    }
}graph;

void build_mst(){
    graph.reset();

    for(int i=1;i<=m;i++){
        graph.mergev(e[i].from,e[i].to);

        for(int f:query[i]){
            closest[f]=graph.trip[graph.root(f)];
        }
    }
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    
    n=N; m=M;
    for(int i=1;i<=m;i++){
        e[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
    }

    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++){
        lt[i]=0; rt[i]=m+1;
    }

    for(int i=1;i<=18;i++){
        for(int f=1;f<=m;f++)query[f].clear();

        for(int f=1;f<=n;f++){
            query[(lt[f]+rt[f])/2].push_back(f);
        }

        build_mst();

        for(int f=1;f<=n;f++){
            if(closest[f]!=0){
                rt[f]=(lt[f]+rt[f])/2;
                special[f]=closest[f];
            }else{
                lt[f]=(lt[f]+rt[f])/2;
            }
        }
    }
}

int getMinimumFuelCapacity(int X, int Y){
    X++; Y++;
    if(rt[X]==m+1)return -1;
    return e[max(rt[X],rt[Y])].cost;
}

/*
int main(){
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});

    cout<<getMinimumFuelCapacity(1, 2)<<"\n";
    cout<<getMinimumFuelCapacity(2,4)<<"\n";
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
}
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6608 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 53 ms 16004 KB Output is correct
10 Correct 64 ms 18060 KB Output is correct
11 Correct 64 ms 17924 KB Output is correct
12 Correct 67 ms 18428 KB Output is correct
13 Correct 56 ms 18796 KB Output is correct
14 Correct 75 ms 16304 KB Output is correct
15 Correct 91 ms 22008 KB Output is correct
16 Correct 91 ms 21604 KB Output is correct
17 Correct 93 ms 22412 KB Output is correct
18 Correct 85 ms 22408 KB Output is correct
19 Incorrect 32 ms 12116 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 97 ms 25708 KB Output is correct
4 Correct 107 ms 26100 KB Output is correct
5 Correct 110 ms 26188 KB Output is correct
6 Correct 110 ms 26032 KB Output is correct
7 Correct 98 ms 26188 KB Output is correct
8 Correct 95 ms 25760 KB Output is correct
9 Correct 97 ms 25928 KB Output is correct
10 Correct 110 ms 25732 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6608 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Incorrect 1 ms 6492 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6608 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 53 ms 16004 KB Output is correct
10 Correct 64 ms 18060 KB Output is correct
11 Correct 64 ms 17924 KB Output is correct
12 Correct 67 ms 18428 KB Output is correct
13 Correct 56 ms 18796 KB Output is correct
14 Correct 75 ms 16304 KB Output is correct
15 Correct 91 ms 22008 KB Output is correct
16 Correct 91 ms 21604 KB Output is correct
17 Correct 93 ms 22412 KB Output is correct
18 Correct 85 ms 22408 KB Output is correct
19 Correct 97 ms 25708 KB Output is correct
20 Correct 107 ms 26100 KB Output is correct
21 Correct 110 ms 26188 KB Output is correct
22 Correct 110 ms 26032 KB Output is correct
23 Correct 98 ms 26188 KB Output is correct
24 Correct 95 ms 25760 KB Output is correct
25 Correct 97 ms 25928 KB Output is correct
26 Correct 110 ms 25732 KB Output is correct
27 Incorrect 2 ms 6492 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -