Submission #401948

#	Time	Username	Problem	Language	Result	Execution time	Memory
401948		Blobo2_Blobo2	Swapping Cities (APIO20_swap)	C++14	0 / 100	2079 ms	21436 KiB

swap

#include "swap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;
#define long long ll
int n,m;
vector<pair<int,int> >adj[200001];
bool vis1[200001];
map<int,int>mp;
bool ok=0;
int idx=1;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n=N,m=M;
    for(int i=0;i<M;i++){
        int x=U[i],y=V[i],c=W[i];
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
}
int dfs1(int u,int des){
    if(u==des)
        return 0;
    vis1[u]=1;
    int ret=1e9+5;
    for(auto v:adj[u])
        if(!vis1[v.first])
            ret=min(ret,max(v.second,dfs1(v.first,des)));
    return ret;
}
int cost=-1;
void dfs2(int u,int des,int c=0){
    if(u==des){
        if(cost==c)
            ok=1;
        return;
    }
    vis1[u]=1;
    for(auto v:adj[u]){
        if(!vis1[v.first]){
            dfs2(v.first,des,max(c,v.second));
            if(ok){
                mp[v.first]=idx;
                idx++;
                return;
            }
        }
    }
    return;
}
int dfs3(int u,int des,int i=1){
    if(u==des)
        return 0;
    vis1[u]=1;
    int ret=1e9+5;
    for(auto v:adj[u]){
        if(!vis1[v.first]&&mp[v.first]!=i){
            int c=max(v.second,dfs3(v.first,des,i+1));
            ret=min(ret,c);
        }
    }
    return ret;
}

int getMinimumFuelCapacity(int x, int y) {
    mp.clear();
    ok=0;
    idx=1;
    cost=-1;
    for(int i=0;i<n;i++)vis1[i]=0;
    cost=dfs1(x,y);
    for(int i=0;i<n;i++)vis1[i]=0;
    dfs2(x,y);
    int mx=0;
    for(int i=0;i<n;i++)
        mx=max(mx,mp[i]);
    mx++;
    for(int i=0;i<n;i++){
        if(!mp[i])continue;
        mp[i]=mx-mp[i];
    }
    for(int i=0;i<n;i++)vis1[i]=0;
    int path2=dfs3(x,y);
    return (max(cost,path2)==(int)1e9+5?-1:max(cost,path2));
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27