oj.uz

Submission #1054844

# Submission time Handle Problem Language Result Execution time Memory
1054844 2024-08-12T12:36:22 Z alexander707070 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 45000 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< pair<int,int> > tree[MAXN];
vector<int> v[MAXN];
int parent[MAXN],res[MAXN],es[MAXN];

struct info{
    int par,mins,maxe;
};

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];
        dsu[x]=root(dsu[x]);
        return 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;

info dp[MAXN][20];
pair<int,int> endz[MAXN];

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

    dp[x][0].par=parent[x];
    dp[x][0].mins=min(res[x],res[parent[x]]);
    dp[x][0].maxe=ee;

    if(res[x]!=inf)last=x;
    endz[x].first=last;

    for(int t=1;t<20;t++){
        dp[x][t].par=dp[dp[x][t-1].par][t-1].par;
        dp[x][t].mins=min( dp[x][t-1].mins , dp[dp[x][t-1].par][t-1].mins );
        dp[x][t].maxe=max( dp[x][t-1].maxe , dp[dp[x][t-1].par][t-1].maxe );
    }

    for(pair<int,int> i:tree[x]){
        if(i.first==p)continue;

        if(res[x]==inf)endz[x].second=dfs(i.first,x,i.second,last);
        else dfs(i.first,x,i.second,last);
    }

    if(res[x]!=inf)return x;
    return endz[x].second;
}

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

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

    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>=(1<<i)){
            ans=min(ans,dp[x][i].mins);
            x=dp[x][i].par;
        }
    }

    for(int i=19;i>=0;i--){
        if(dp[x][i].par!=0 and dp[y][i].par!=0 and dp[x][i].par!=dp[y][i].par){
            ans=min(ans,dp[x][i].mins);
            ans=min(ans,dp[y][i].mins);

            x=dp[x][i].par; y=dp[y][i].par;
        }
    }

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

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

    int ans=0;
    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>(1<<i)){
            ans=max(ans,dp[x][i].maxe);
            x=dp[x][i].par;
        }
    }

    ans=max(ans,dp[x][0].maxe);
    if(parent[x]==y)return ans;
    
    x=dp[x][0].par;

    for(int i=19;i>=0;i--){
        if(dp[x][i].par!=0 and dp[y][i].par!=0 and dp[x][i].par!=dp[y][i].par){
            ans=max(ans,dp[x][i].maxe);
            ans=max(ans,dp[y][i].maxe);

            x=dp[x][i].par; y=dp[y][i].par;
        }
    }

    ans=max(ans,max(dp[x][0].maxe,dp[y][0].maxe));

    return ans;
}

int best[MAXN];

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,e[i].cost});
        tree[e[i].to].push_back({e[i].from,e[i].cost});

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

    for(int t=0;t<20;t++)dp[0][t]={0,inf,0};
    dfs(1,0,0,0);

    for(int i=1;i<=n;i++){
        best[i]=i;

        for(int f=1;f<=n;f++){
            if(max(res[f],getedge(i,f))<max(res[best[i]],getedge(i,best[i])))best[i]=f;
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++; Y++;
    //vector<int> bros={endz[X].first,endz[X].second,endz[Y].first,endz[Y].second};

    int ans=inf,k=best[X];
    ans=min(ans,max(res[k],max(getedge(X,k),getedge(Y,k))));
    k=best[Y];
    ans=min(ans,max(res[k],max(getedge(X,k),getedge(Y,k))));

    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 12888 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 21 ms 12816 KB Output is correct
5 Correct 104 ms 12856 KB Output is correct
6 Correct 96 ms 12636 KB Output is correct
7 Correct 124 ms 12868 KB Output is correct
8 Correct 109 ms 13152 KB Output is correct
9 Execution timed out 2080 ms 42436 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12888 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Execution timed out 2048 ms 45000 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 12888 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 21 ms 12816 KB Output is correct
5 Correct 104 ms 12856 KB Output is correct
6 Correct 96 ms 12636 KB Output is correct
7 Correct 124 ms 12868 KB Output is correct
8 Correct 109 ms 13152 KB Output is correct
9 Incorrect 1 ms 12636 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 12636 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 12888 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 21 ms 12816 KB Output is correct
5 Correct 104 ms 12856 KB Output is correct
6 Correct 96 ms 12636 KB Output is correct
7 Correct 124 ms 12868 KB Output is correct
8 Correct 109 ms 13152 KB Output is correct
9 Execution timed out 2080 ms 42436 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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