oj.uz

Submission #1054774

# Submission time Handle Problem Language Result Execution time Memory
1054774 2024-08-12T12:04:49 Z alexander707070 Swapping Cities (APIO20_swap) C++14
7 / 100
 111 ms 49736 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];

void dfs(int x,int p,int ee){
    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;

    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;
        dfs(i.first,x,i.second);
    }
}

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,dp[x][i].mins);
                x=dp[x][i].par;
            }
        }
        
        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(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;
        }
    }

    if(parent[x]==y)return ans;
    
    ans=max(ans,dp[x][0].maxe);
    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;
        }
    }

    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,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);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans=max( max(es[X+1],es[Y+1]) , min(res[X+1],min(res[Y+1],res[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 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Correct 56 ms 38324 KB Output is correct
10 Correct 68 ms 45392 KB Output is correct
11 Correct 69 ms 44916 KB Output is correct
12 Correct 68 ms 45904 KB Output is correct
13 Correct 69 ms 46996 KB Output is correct
14 Correct 59 ms 37972 KB Output is correct
15 Correct 93 ms 47376 KB Output is correct
16 Correct 97 ms 46192 KB Output is correct
17 Correct 105 ms 48932 KB Output is correct
18 Correct 111 ms 48252 KB Output is correct
19 Incorrect 33 ms 18256 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 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 74 ms 45416 KB Output is correct
4 Correct 81 ms 49712 KB Output is correct
5 Correct 83 ms 49732 KB Output is correct
6 Correct 81 ms 49564 KB Output is correct
7 Correct 77 ms 49736 KB Output is correct
8 Correct 75 ms 49268 KB Output is correct
9 Correct 76 ms 49544 KB Output is correct
10 Correct 75 ms 49028 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Incorrect 1 ms 8796 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 8796 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 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Correct 56 ms 38324 KB Output is correct
10 Correct 68 ms 45392 KB Output is correct
11 Correct 69 ms 44916 KB Output is correct
12 Correct 68 ms 45904 KB Output is correct
13 Correct 69 ms 46996 KB Output is correct
14 Correct 59 ms 37972 KB Output is correct
15 Correct 93 ms 47376 KB Output is correct
16 Correct 97 ms 46192 KB Output is correct
17 Correct 105 ms 48932 KB Output is correct
18 Correct 111 ms 48252 KB Output is correct
19 Correct 74 ms 45416 KB Output is correct
20 Correct 81 ms 49712 KB Output is correct
21 Correct 83 ms 49732 KB Output is correct
22 Correct 81 ms 49564 KB Output is correct
23 Correct 77 ms 49736 KB Output is correct
24 Correct 75 ms 49268 KB Output is correct
25 Correct 76 ms 49544 KB Output is correct
26 Correct 75 ms 49028 KB Output is correct
27 Incorrect 2 ms 11320 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 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -