제출 #292533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292533		daniel920712	자매 도시 (APIO20_swap)	C++14	0 / 100	2100 ms	25820 KiB

swap

#include "swap.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
int NN;
int MM;
int what[200005]={0};
int what2[200005];
int all[200005];
int big[200005]={0};
int deg[200005]={0};
int con[200005]={0};
bool use[200005];
bool use2[200005];

int Father[200005];
int y;
int ans=0;
vector < pair < pair < int , int > , int > > Next[200005];
vector < pair < pair < int , int > , int > > Next2[200005];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int >  > > dd;
struct A
{
    int u,v,w;
    int con;
}edge[200005];
vector < int > have;
bool cmp(pair < pair < int , int > , int > a,pair < pair < int , int > , int > b)
{
    return a.first.second<b.first.second;
}
bool cmp2(A a,A b)
{
    return a.w<b.w;
}
bool F(int here,int fa)
{
    what[here]=fa;
    if(here==y)
    {
        have.push_back(here);
        return 1;
    }
    for(auto i:Next2[here])
    {
        if(i.first.first==fa) continue;

        if(F(i.first.first,here))
        {
            ans=max(ans,i.first.second);
            use[i.second]=1;
            have.push_back(here);
            return 1;

        }
    }
    return 0;
}
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W)
{
    NN=N;
    MM=M;
    int i;
    con[0]=N-1;
    for(i=0;i<M;i++)
    {
        Next[U[i]].push_back(make_pair(make_pair(V[i],W[i]),i));
        Next[V[i]].push_back(make_pair(make_pair(U[i],W[i]),i));

        edge[i].u=U[i];
        edge[i].v=V[i];
        edge[i].w=W[i];
        edge[i].con=i;
    }
    for(i=0;i<N;i++)
    {
        Father[i]=i;
        sort(Next[i].begin(),Next[i].end(),cmp);
    }
    sort(edge,edge+M,cmp2);
    for(i=0;i<M;i++)
    {
        if(Find(edge[i].u)==Find(edge[i].v)) continue;
        Father[Find(edge[i].u)]=Find(edge[i].v);
        Next2[edge[i].u].push_back(make_pair(make_pair(edge[i].v,edge[i].w),edge[i].con));
        Next2[edge[i].v].push_back(make_pair(make_pair(edge[i].u,edge[i].w),edge[i].con));
        //printf("%d\n",i);
    }



}

int getMinimumFuelCapacity(int x, int y)
{
    int t=2e9,t2=-1,con=0,i,j,a,b;
    ::y=y;
    for(i=0;i<MM;i++) use[i]=0;
    ans=0;
    have.clear();
    F(x,-1);
    for(auto i:have)
    {
        con=0;
        t2=-1;
        if(i==x||i==y) continue;
        for(auto j:Next[i])
        {
            if(use[j.second]) continue;
            con++;
            if(con>=1)
            {
                t2=j.first.second;
                break;
            }

        }
        if(t2!=-1) t=min(t,t2);

    }
    //for(i=0;i<MM;i++) printf("%d %d\n",i,use[i]);
    for(auto i:Next[x])
    {
        //printf("aa %d %d %d %d\n",i.first.second,i.first.second,i.second,use[i.second]);
        if(use[i.second]) continue;
        for(j=0;j<NN;j++) use2[j]=0;
        dd.push(make_pair(i.first.second,i.first.first));
        //printf("aa %d %d %d\n",i.first.second,i.first.second,i.second);
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b]) continue;
            //printf("%d %d\n",a,b);
            if(b==y)
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(j.second==i.second) continue;
                dd.push(make_pair(max(j.first.second,a),j.first.first));

            }
        }
        while(!dd.empty()) dd.pop();

    }
    if(t>=2000000000) return -1;
    //printf("%d %d\n",ans,t);
    return max(t,ans);




}

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