Submission #1272187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272187		StefanSebez	Swapping Cities (APIO20_swap)	C++20	0 / 100	2095 ms	15708 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,inf=1e9+50;
vector<pair<int,int>>E[N];
int n,m;
int Val[N];
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W) {
    n=n1,m=m1;
    for(int i=0;i<m;i++){
        E[U[i]].pb({V[i],W[i]});
        E[V[i]].pb({U[i],W[i]});
    }
    for(int i=0;i<n;i++){
        sort(E[i].begin(),E[i].end(),[&](pair<int,int>a,pair<int,int>b){return a.se<b.se;});
        if(E[i].size()<3) Val[i]=inf+100;
        else Val[i]=E[i][2].se;
    }
}
bool was[N],ciklus;
int par[N],deg[N];
void DFS(int u,int mid,int p=-1){
    was[u]=true;
    for(auto [v,w]:E[u]){
        if(w>mid) continue;
        if(was[v]&&v!=p) ciklus=true;
        if(!was[v]){
            par[v]=u;
            deg[u]++,deg[v]++;
            DFS(v,mid,u);
        }
    }
}
int getMinimumFuelCapacity(int X,int Y) {
    int l=0,r=inf,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        for(int i=0;i<=n;i++) was[i]=false,par[i]=deg[i]=0;ciklus=false;
        DFS(X,mid);
        if(!was[Y]){l=mid+1;continue;}
        if(ciklus){res=mid;r=mid-1;continue;}
        int mn=inf+1000;
        int v=par[Y];
        bool moze=false;
        while(v!=X){
            //mn=min(mn,Val[v]);
            if(deg[v]>2) moze=true;
            v=par[v];
        }
        if(moze){res=mid;r=mid-1;}
        else l=mid+1;
    }
    return res;
}

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