oj.uz

Submission #1054627

# Submission time Handle Problem Language Result Execution time Memory
1054627 2024-08-12T11:10:36 Z alexander707070 Swapping Cities (APIO20_swap) C++14
0 / 100
 218 ms 41908 KB 
#include<bits/stdc++.h>
#include "swap.h"

#define MAXN 100007
using namespace std;

const int inf=1e9+7;

int n,m,a[MAXN],b[MAXN],c[MAXN],dep[MAXN];
vector<int> tree[MAXN],v[MAXN];
int parent[MAXN],res[MAXN];

struct edge{
    int from,to,cost;

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

struct unionfind{
    int dsu[MAXN],sz[MAXN];

    void init(){
        for(int i=1;i<=n;i++){
            dsu[i]=i; sz[i]=1;
        }
    }

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

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

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

        dsu[rooty]=rootx;
        sz[rootx]+=sz[rooty];
    }

    bool connected(int x,int y){
        return root(x)==root(y);
    }
}graph;

void dfs(int x,int p){
    parent[x]=p;
    dep[x]=dep[p]+1;

    for(int i:tree[x]){
        if(i==p)continue;
        dfs(i,x);
    }
}

pair<int,int> dp[MAXN][20];
bool li[MAXN][20];

pair<int,int> ff(int x,int p){
    if(p==0)return {parent[x],min(res[x],res[parent[x]])};
    if(x==0)return {0,inf};

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
    dp[x][p].second=min( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );

    return dp[x][p];
}

int getbranch(int x,int y){
    int ans=inf;

    if(dep[x]<dep[y])swap(x,y);

    if(x==y or parent[x]==y)return inf;

    if(dep[x]!=dep[y]){
        x=parent[x];

        for(int i=19;i>=0;i--){
            if(dep[x]-dep[y]>(1<<i)){
                ans=min(ans,ff(x,i).second);
                x=ff(x,i).first;
            }
        }
        
        if(parent[x]==y)return ans;

        if(dep[x]>dep[y]){
            x=parent[x];
            ans=min(ans,res[x]);
        }
    }

    x=parent[x];
    y=parent[y];

    ans=min(ans,res[x]);

    for(int i=19;i>=0;i--){
        if(ff(x,i).first!=0 and ff(y,i).first!=0 and ff(x,i).first!=ff(y,i).first){
            ans=min(ans,ff(x,i).second);
            ans=min(ans,ff(y,i).second);

            x=ff(x,i).first; y=ff(y,i).first;
        }
    }

    if(x!=y)ans=min(ans,res[parent[x]]);

    return ans;
}

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++){
        a[i]=U[i-1]+1; b[i]=V[i-1]+1; c[i]=W[i-1];

        v[a[i]].push_back(c[i]);
        v[b[i]].push_back(c[i]);

        e[i]={a[i],b[i],c[i]};
    }

    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());

        res[i]=inf;
        if(v[i].size()>=3)res[i]=v[i][2];
    }
    res[0]=inf;

    sort(e+1,e+m+1);
    graph.init();

    for(int i=1;i<=m;i++){
        if(graph.connected(e[i].from,e[i].to))continue;
        
        tree[e[i].from].push_back(e[i].to);
        tree[e[i].to].push_back(e[i].from);

        graph.mergev(e[i].from,e[i].to);
    }

    dfs(1,0);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans=getbranch(X+1,Y+1);

    if(ans==inf)return -1;
    return ans;
}

/*
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 8792 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 43 ms 32236 KB Output is correct
10 Correct 53 ms 37612 KB Output is correct
11 Correct 48 ms 37108 KB Output is correct
12 Correct 59 ms 37820 KB Output is correct
13 Correct 52 ms 39096 KB Output is correct
14 Correct 72 ms 32180 KB Output is correct
15 Correct 184 ms 40416 KB Output is correct
16 Correct 218 ms 38976 KB Output is correct
17 Correct 162 ms 41908 KB Output is correct
18 Correct 177 ms 41032 KB Output is correct
19 Incorrect 58 ms 18256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Incorrect 1 ms 10844 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 10844 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 8792 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 43 ms 32236 KB Output is correct
10 Correct 53 ms 37612 KB Output is correct
11 Correct 48 ms 37108 KB Output is correct
12 Correct 59 ms 37820 KB Output is correct
13 Correct 52 ms 39096 KB Output is correct
14 Correct 72 ms 32180 KB Output is correct
15 Correct 184 ms 40416 KB Output is correct
16 Correct 218 ms 38976 KB Output is correct
17 Correct 162 ms 41908 KB Output is correct
18 Correct 177 ms 41032 KB Output is correct
19 Incorrect 71 ms 23408 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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