oj.uz

Submission #1054619

# Submission time Handle Problem Language Result Execution time Memory
1054619 2024-08-12T11:07:21 Z alexander707070 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 44204 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];

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

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

    void mergev(int x,int y){
        if(root(x)==root(y))return;

        dsu[root(x)]=root(y);
    }

    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 8540 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10844 KB Output is correct
9 Correct 41 ms 33216 KB Output is correct
10 Correct 48 ms 38632 KB Output is correct
11 Correct 51 ms 38136 KB Output is correct
12 Correct 61 ms 39100 KB Output is correct
13 Correct 51 ms 40256 KB Output is correct
14 Correct 73 ms 33212 KB Output is correct
15 Correct 183 ms 42636 KB Output is correct
16 Correct 197 ms 41420 KB Output is correct
17 Correct 172 ms 44204 KB Output is correct
18 Correct 180 ms 43196 KB Output is correct
19 Incorrect 65 ms 19436 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 8540 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Execution timed out 2037 ms 19588 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 8540 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10844 KB Output is correct
9 Incorrect 1 ms 10588 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 10588 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 8540 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10844 KB Output is correct
9 Correct 41 ms 33216 KB Output is correct
10 Correct 48 ms 38632 KB Output is correct
11 Correct 51 ms 38136 KB Output is correct
12 Correct 61 ms 39100 KB Output is correct
13 Correct 51 ms 40256 KB Output is correct
14 Correct 73 ms 33212 KB Output is correct
15 Correct 183 ms 42636 KB Output is correct
16 Correct 197 ms 41420 KB Output is correct
17 Correct 172 ms 44204 KB Output is correct
18 Correct 180 ms 43196 KB Output is correct
19 Execution timed out 2037 ms 19588 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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