제출 #918866

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

swap

#include<bits/stdc++.h>
#include"swap.h"
#define taskname ""
#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;
struct edge
{
    int u,v,w,used;
}e[maxn];
bool operator <(edge a,edge b)
{
    return a.w<b.w;
}
vector<int> adj[maxn];
vector<int> gg[maxn];
int up[maxn][20],f[maxn][20],g[maxn][20],n,m,par[maxn],h[maxn],v[maxn],d[maxn],vis[maxn];
int fp(int x)
{
    if(par[x]<0) return x;
    return par[x]=fp(par[x]);
}
void uni(int a,int b,int i)
{
    a=fp(a);
    b=fp(b);
    if(a==b) return;
    e[i].used=1;
    if(par[a]>par[b]) swap(a,b);
    par[a]+=par[b];
    par[b]=a;
}
void dfs(int x,int par)
{
    up[x][0]=par;
    h[x]=h[par]+1;
    for(int i:adj[x])
    {
        if(e[i].used==0) continue;
        int y=e[i].u+e[i].v-x;
        if(y==par) continue;
        f[y][0]=e[i].w;
        dfs(y,x);
    }
}
int lca(int a,int b)
{
    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)) a=up[a][i];
        }
    }
    if(a==b) return a;
    else
    {
        int lg=__lg(h[b]);
        for(int i=lg;i>=0;i--)
        {
            if(up[a][i]!=up[b][i])
            {
                a=up[a][i];
                b=up[b][i];
            }
        }
        return up[a][0];
    }
}
int findf(int x,int w)
{
    int ans=0;
    for(int i=0;i<20;i++)
    {
        if(w&(1<<i))
        {
            ans=max(ans,f[x][i]);
            x=up[x][i];
        }
    }
    return ans;
}
int findg(int x,int w)
{
    int ans=INF;
    for(int i=0;i<20;i++)
    {
        if(w&(1<<i))
        {
            ans=min(ans,g[x][i]);
            x=up[x][i];
        }
    }
    return ans;
}
void updg(int x,int w,int val)
{
    for(int i=0;i<20;i++)
    {
        if(w&(1<<i))
        {
            g[x][i]=min(g[x][i],val);
            x=up[x][i];
        }
    }
}
void upd(int a,int b,int val)
{
    int p=lca(a,b);
    int wa=findf(a,h[a]-h[p]);
    int wb=findf(b,h[b]-h[p]);
    val=max({wb,wa,val});
    updg(a,h[a]-h[p],val);
    updg(b,h[b]-h[p],val);
}
void dijkstra()
{
    priority_queue<pii> pq;
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        pq.push({-v[i],i});
    }
    while(!pq.empty())
    {
        int x=pq.top().sc;
        int dis=-pq.top().fi;
        pq.pop();
        if(vis[x]) continue;
        vis[x]=1;
        d[x]=dis;
        for(int i:gg[x])
        {
            int y=e[i].u+e[i].v-x;
            pq.push({-max(dis,e[i].w),i});
        }
    }
    for(int i=1;i<=n;i++)
    {
        v[i]=d[i];
    }
}
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++)
    {
        par[i]=-1;
    }
    for(int i=1;i<=m;i++)
    {
        uni(e[i].u,e[i].v,i);
        if(e[i].used==1)
        {
            adj[e[i].u].push_back(i);
            adj[e[i].v].push_back(i);
        }
        gg[e[i].u].push_back(i);
        gg[e[i].v].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<20;j++)
        {
            g[i][j]=INF;
        }
        v[i]=INF;
    }
    for(int i=1;i<20;i++)
    {
        for(int j=1;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]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(e[i].used==0)
        {
            upd(e[i].u,e[i].v,e[i].w);
        }
    }
    for(int i=3;i;i--)
    {
        for(int j=1;j<=n;j++)
        {
            g[j][i-1]=min(g[j][i-1],g[j][i]);
            g[up[j][i-1]][i-1]=min(g[up[j][i-1]][i-1],g[j][i]);
//            cout<<g[j][i]<<" ";
        }
//        cout<<"\n";
    }
    for(int i=1;i<=n;i++)
    {
        v[i]=min(v[i],g[i][0]);
        v[up[i][0]]=min(v[up[i][0]],g[i][0]);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<20;j++)
        {
            g[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++)
    {
        g[i][0]=min(v[i],v[up[i][0]]);
    }
    for(int i=1;i<20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            g[j][i]=min(g[j][i-1],g[up[j][i-1]][i-1]);
        }
    }
}
int getMinimumFuelCapacity(int a,int b)
{
    int p=lca(a,b);
    int wa=findf(a,h[a]-h[p]);
    int wb=findf(b,h[b]-h[p]);
    int wwa=findg(a,h[a]-h[p]);
    int wwb=findg(b,h[b]-h[p]);
    int lmao=min(wwa,wwb);
    if(lmao==INF) return -1;
    return max({wa,wb,lmao});
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".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++)
//    {
//        for(int j=0;j<=1;j++)
//        {
//            cout<<g[i][j]<<" ";
//        }
//        cout<<"\n";
//    }
//    for(int i=1;i<=n;i++) cout<<v[i]<<" ";
//}

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void dijkstra()':
swap.cpp:147:17: warning: unused variable 'y' [-Wunused-variable]
  147 |             int y=e[i].u+e[i].v-x;
      |                 ^

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