제출 #919772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919772		User0069	자매 도시 (APIO20_swap)	C++17	0 / 100	5 ms	20824 KiB

swap

#include<bits/stdc++.h>
#include"swap.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int long long
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+6;
const int INF=1e9+1;
int n,m,f[maxn][20],par[maxn],v[maxn],cnt[maxn];
struct edge
{
    int u,v,w,used;
} e[maxn];
bool operator <(edge a,edge b)
{
    return a.w<b.w;
}
int fp(int x)
{
    if(par[x]<0) return x;
    return par[x]=fp(par[x]);
}
void uni(int a,int b)
{
    a=fp(a);
    b=fp(b);
    if(a==b) return;
    if(par[a]>par[b]) swap(a,b);
    par[a]+=par[b];
    par[b]=a;
}
struct tree
{
    int up[maxn][20],h[maxn],f[maxn][20];
    vector<int> adj[maxn];
    void dfs(int x,int par,int w)
    {
        up[x][0]=par;
        h[x]=h[par]+1;
        f[x][0]=w;
        for(int i:adj[x])
        {
            int y=e[i].u+e[i].v-x;
            if(y==par) continue;
            dfs(y,x,e[i].w);
        }
    }
    void buildST(bool wow)
    {
        for(int i=1; i<=n; i++)
        {
            if(up[i][0]==0) dfs(i,0,INF);
        }
        if(wow)
        {
            v[0]=INF;
            f[0][0]=-INF;
            for(int i=1;i<=n;i++)
            {
                f[i][0]=-min(v[i],v[up[i][0]]);
            }
        }
        for(int i=1; i<20; i++)
        {
            for(int j=0; j<=n; j++)
            {
                up[j][i]=up[up[j][i-1]][i-1];
                f[j][i]=max(f[j][i-1],f[up[j][i-1]][i-1]);
            }
        }
    }
    int get(int a,int b)
    {
        int ans=-INF;
        if(h[a]<h[b]) swap(a,b);
        if(h[a]!=h[b])
        {
            int dif=h[a]-h[b];
            for(int i=0;i<20;i++)
            {
                if(dif&(1<<i))
                {
                    ans=max(ans,f[a][i]);
                    a=up[a][i];
                }
            }
        }
        if(a==b) return ans;
        else
        {
            for(int i=19;i>=0;i--)
            {
                if(up[a][i]!=up[b][i])
                {
                    ans=max(ans,f[a][i]);
                    ans=max(ans,f[b][i]);
                    a=up[a][i];
                    b=up[b][i];
//                    cout<<ans<<"!\n";
                }
            }
            ans=max(ans,f[a][0]);
            ans=max(ans,f[b][0]);
//            cout<<ans<<"!\n";
            return ans;
        }
    }
} f1,f2,f3;
void init(int n_,int m_,vector<int> u_,vector<int> v_,vector<int> w_)
{
    n=n_;
    m=m_;
    for(int i=0; i<(int) u_.size(); i++)
    {
        e[i+1]= {u_[i]+1,v_[i]+1,w_[i],0};
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++)
    {
        v[i]=INF;
    }
    for(int i=1;i<=m;i++)
    {
        if(++cnt[e[i].u]==3)
        {
            v[e[i].u]=e[i].w;
        }
        if(++cnt[e[i].v]==3)
        {
            v[e[i].v]=e[i].w;
        }
    }
    for(int i=1;i<=n;i++)
    {
        par[i]=-1;
    }
    for(int i=1; i<=m; i++)
    {
        if(fp(e[i].u)!=fp(e[i].v))
        {
            uni(e[i].u,e[i].v);
            f1.adj[e[i].u].push_back(i);
            f1.adj[e[i].v].push_back(i);
            f3.adj[e[i].u].push_back(i);
            f3.adj[e[i].v].push_back(i);
            e[i].used=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        par[i]=-1;
    }
    for(int i=1; i<=m; i++)
    {
        if(e[i].used==0&&fp(e[i].u)!=fp(e[i].v))
        {
            uni(e[i].u,e[i].v);
            f2.adj[e[i].u].push_back(i);
            f2.adj[e[i].v].push_back(i);
            e[i].used=1;
        }
    }
    f1.buildST(0);
    f2.buildST(0);
    f3.buildST(1);
}
int getMinimumFuelCapacity(int a,int b)
{
    int w1=f1.get(a,b);
    int w2=f2.get(a,b);
    int w3=f3.get(a,b);
    w3=-w3;
    return max(min(w2,w3),w1);
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int n,m,q;
//    vector<int> v1,v2,v3;
//    cin>>n>>m>>q;
//    for(int i=1; i<=m; i++)
//    {
//        int u,v,w;
//        cin>>u>>v>>w;
//        v1.push_back(u);
//        v2.push_back(v);
//        v3.push_back(w);
//    }
//    init(n,m,v1,v2,v3);
//    while(q--)
//    {
//        int u,v;
//        cin>>u>>v;
//        cout<<getMinimumFuelCapacity(++u,++v)<<"\n";
//    }
////    for(int i=1;i<=n;i++)
////    {
////        cout<<f1.f[i][0]<<"\n";
////    }
////    cout<<f1.get(3,4)<<"\n";
//}

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