제출 #292531

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

swap

#include "swap.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
int NN;
int MM;
int all[200005];
bool use[200005];
bool use2[200005];
bool have2[200005];
bool have3[200005];
int Father[200005];
int y;
int ans=0;
int how=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)
{
    if(here==y)
    {
        //printf("%d\n",here);
        have.push_back(here);
        have2[here]=1;
        return 1;
    }
    for(auto i:Next2[here])
    {
        if(i.first.first==fa) continue;
        if(F(i.first.first,here))
        {
            //printf("%d\n",here);
            ans=max(ans,i.first.second);
            use[i.second]=1;
            have.push_back(here);
            have2[here]=1;
            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;
    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));
    }
}

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;
    for(i=0;i<=NN;i++) have2[i]=0;
    ans=0;
    have.clear();
    F(x,-1);
    for(auto i:have)
    {
        con=0;
        t2=-1;
        for(auto j:Next[i])
        {
            if(use[j.second]) continue;
            //if(i==x||i==y) printf("%d %d\n",i,j.first.second);
            con++;

            if((i!=x&&i!=y&&con>=1)||con>=2)
            {
                //printf("%d %d\n",i,j.first.second);
                t2=j.first.second;
                break;
            }

        }
        if(t2!=-1) t=min(t,t2);
    }
    for(auto i:Next[x])
    {
        if(use[i.second]) continue;
        for(j=0;j<=NN;j++) use2[j]=0;
        for(j=0;j<=MM;j++) have3[j]=0;
        have3[i.second]=1;
        dd.push(make_pair(i.first.second,i.first.first));
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b])
            {
                t=min(t,a);
                break;
            }
            if(have2[b])
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(have3[j.second]||use[j.second]) continue;
                have3[j.second]=1;
                dd.push(make_pair(max(j.first.second,a),j.first.first));

            }
        }
        while(!dd.empty()) dd.pop();
    }
    for(auto i:Next[y])
    {
        if(use[i.second]) continue;
        for(j=0;j<=NN;j++) use2[j]=0;
        for(j=0;j<=MM;j++) have3[j]=0;
        have3[i.second]=1;
        dd.push(make_pair(i.first.second,i.first.first));
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b])
            {
                t=min(t,a);
                break;
            }
            if(have2[b])
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(have3[j.second]||use[j.second]) continue;
                have3[j.second]=1;
                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",t,ans);
    return max(t,ans);
    //return 0;
}

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