제출 #560304

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

swap

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  
#include "swap.h"

using namespace std;

const int N = (int)1e5+228;
const int M = (int)2e5+228;
const int INF = (int)1e9+7;
const int logn = 17;

int n , m , par[N] , dad[N][logn+1] , b[N];
int h[N] , f[N][logn+1] , g[N][logn+1];
vector<pii> adj1[N] , adj2[N];
bool mark1[M] , mark2[N];

struct edge
{
    int u , v , w;
    bool operator < (const edge &x) const
    {
        return w < x.w;
    }
}edges[M];

struct DisjointSet
{
    vector<int> lab;
    int n;
    DisjointSet(int _n = 0)
    {
        n = _n;
        lab.assign(n+7 , -1);
    }
    int Find(int u)
    {
        if(lab[u] < 0) return u;
        return lab[u] = Find(lab[u]);
    }
    bool join(int u , int v)
    {
        u = Find(u) , v = Find(v);
        if(u == v) return false;
        if(lab[u] < lab[v]) swap(u , v);
        lab[v] += lab[u] , lab[u] = v;
        return true;
    }
}dsu;

void dfs(int u , int prv)
{
    b[u] = prv;
    if(u != 0)
    {
        for(int i=0 ; i<(int)adj2[par[u]].size() ; ++i)
        {
            int id = adj2[par[u]][i].se;
            if(id != b[par[u]] && id != prv)
            {
                f[u][0] = edges[id].w;
                break;
            }
        }
    }
    for(int j=1 ; j<=logn ; ++j)
    {
        f[u][j] = min(f[u][j-1] , f[dad[u][j-1]][j-1]);
    }
    for(int i=0 ; i<(int)adj1[u].size() ; ++i)
    {
        int v = adj1[u][i].fi , id = adj1[u][i].se;
        if(id == prv || v == par[u]) continue;
        par[v] = u , h[v] = h[u] + 1 , dad[v][0] = u , g[v][0] = edges[id].w;
        for(int j=1 ; j<=logn ; ++j) 
        {
            dad[v][j] = dad[dad[v][j-1]][j-1];
            g[v][j] = max(g[v][j-1] , g[dad[v][j-1]][j-1]);
        }
        dfs(v , id); 
    }

}

void init(int _n, int _m,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = _n , m = _m;
    for(int i=0 ; i<m ; ++i) edges[i].u = U[i] , edges[i].v = V[i] , edges[i].w = W[i];
    sort(edges , edges+m);
    dsu = DisjointSet(n);
    for(int i=0 ; i<m ; ++i)
    {
        int u = edges[i].u , v = edges[i].v;
        adj2[u].push_back(make_pair(v , i));
        adj2[v].push_back(make_pair(u , i));
        if(dsu.join(u , v))
        {
            adj1[u].push_back(make_pair(v , i));
            adj1[v].push_back(make_pair(u , i));
        }
    }
    memset(f , 0x3f , sizeof(f));
    h[0] = 1;
    dfs(0 , -1);
    // for(int i=0 ; i<m ; ++i) cout << edges[i].w << " ";
    //     cout << '\n';
}

int getMin(int u , int v)
{
    int x = u , y = v;
    for(int i=0 ; i<m ; ++i) mark1[i] = false;
    for(int i=0 ; i<n ; ++i) mark2[i] = false;
    if(h[u] < h[v]) swap(u , v);
    while(h[u] > h[v])
    {
        mark2[u] = true;
        mark1[b[u]] = true;
        u = par[u];
    }
    while(u != v)
    {
        mark2[u] = mark2[v] = true;
        mark1[b[u]] = mark1[b[v]] = true;
        u = par[u] , v = par[v];
    }
    mark2[u] = true;
    for(int i=0 ; i<m ; ++i)
    {
        if(mark1[i]) continue;
        if(mark2[edges[i].u] && edges[i].u != x && edges[i].u != y) return edges[i].w;
        if(mark2[edges[i].v] && edges[i].v != x && edges[i].v != y) return edges[i].w;
    }
    return INF;
}

int getMax(int u , int v)
{
    int res = 0;
    if(h[u] < h[v]) swap(u , v);
    for(int i=logn ; i>=0 ; --i) 
    {
        if(h[dad[u][i]] >= h[v])
        {
            res = max(res , g[u][i]);
            u = dad[u][i];
        }
    }
    if(u == v) return res;
    for(int i=logn ; i>=0 ; --i)
    {
        if(dad[u][i] != dad[v][i]) 
        {
            res = max(res , max(g[u][i] , g[v][i]));
            u = dad[u][i] , v = dad[v][i];
        }
    }
    res = max(res , max(g[u][0] , g[v][0]));
    return res;
}

vector<int> adj3[N];
int low[N] , num[N] , inID[N] , t , cur;
stack<int> st;

void tarjan(int u , int p)
{
    low[u] = num[u] = ++t;
    st.push(u);
    for(int v : adj3[u])
    {
        if(v == p) continue;
        if(num[v]) low[u] = min(low[u] , num[v]);
        else 
        {
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
        }
    }
    if(low[u] == num[u])
    {
        ++cur;
        int v;
        do 
        {
            v = st.top();
            st.pop();
            inID[v] = cur;
            low[v] = num[v] = INF;
        }
        while(u != v);
    }
}

bool check(int mid , int X , int Y)
{
    for(int i=0 ; i<n ; ++i) adj3[i].clear() , low[i] = num[i] = inID[i] = 0;
    t = 0 , cur = 0;
    for(int i=0 ; i<=mid ; ++i)
    {
        int u = edges[i].u , v = edges[i].v;
        adj3[u].push_back(v) , adj3[v].push_back(u);
    }
    for(int i=0 ; i<n ; ++i) if(!num[i]) tarjan(i , -1);
    return (inID[X] == inID[Y]);
}

int getMinimumFuelCapacity(int X, int Y) {
    int tmp1 = getMin(X , Y) , tmp2 = getMax(X , Y);
    int res = max(tmp1 , tmp2);
    if(m == n-1) 
    {
        if(res >= INF) return -1;
        return res;
    }
    int l = 0 , r = m-1 , tmp3 = INF;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check(mid , X , Y))
        {
            tmp3 = edges[mid].w;
            r = mid-1;
        }
        else l = mid+1;
    }
    res = min(res , tmp3);
    if(res >= INF) return -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