제출 #916091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916091		duckindog	자매 도시 (APIO20_swap)	C++14	73 / 100	2098 ms	56264 KiB

swap

#include<bits/stdc++.h>

using namespace std;

//#define LOCAL

#ifndef LOCAL
#include "swap.h"
#endif // LOCAL

const int N = 1e5 + 10;

int n, m;
vector<pair<int, int>> ad[N];

//tree
int f[N][17], g[N][17], dp[N][17], st[N], ed[N], it;
int dpin[N], dpout[N];
void dfs(int u, int pre = -1) {
  st[u] = ++it;

  for (int i = 1; i <= 16; ++i) {
    f[u][i] = f[f[u][i - 1]][i - 1];
    g[u][i] = max(g[u][i - 1], g[f[u][i - 1]][i - 1]);
    dp[u][i] = min(dp[u][i - 1], dp[f[u][i - 1]][i - 1]);
  }

  vector<pair<int, int>> best;
  sort(ad[u].begin(), ad[u].end(), [&] (auto& a, auto& b) {
    return a.second < b.second;
  });

  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre) continue;
    best.push_back({w, v});
  }

  sort(best.begin(), best.end());
  dpin[u] = 1e9 + 1;
  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre) continue;

    f[v][0] = u;
    g[v][0] = w;

    if (best.size() >= 2) {
      dp[v][0] = (best[0].second != v ? best[0].first : best[1].first);
    } else dp[v][0] = 1e9 + 1;

    dfs(v, u);
    dpin[u] = min(dpin[u], max(w, dpin[v]));
  }

  if (best.size() >= 2) {
    dpin[u] = min(dpin[u], best[1].first);
  }

  ed[u] = it;
}
void dfs_out(int u, int pre = 0) {

  vector<pair<int, int>> best, bestmax;
  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    best.push_back({w, v});
    if (v == pre) continue;
    bestmax.push_back({max(w, dpin[v]), v});
  }
  sort(best.begin(), best.end());
  sort(bestmax.begin(), bestmax.end());

  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre) continue;
    dpout[v] = dpout[u];

    if (bestmax.size() >= 2) {
      dpout[v] = min(dpout[v], bestmax[0].second != v ? bestmax[0].first : bestmax[1].first);
    }

    if (best.size() >= 3) {
      if (best[0].second != v && best[1].second != v) dpout[v] = min(dpout[v], best[1].first);
      else dpout[v] = min(dpout[v], best[2].first);

    }
    dpout[v] = max(w, dpout[v]);
    dfs_out(v, u);
  }

}

bool anc(int u, int v) {
  return st[u] <= st[v] && ed[u] >= ed[v];
}
int lca(int u, int v) {
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;

  for (int i = 16; i >= 0; --i)
    if (!anc(f[u][i], v)) u = f[u][i];
  return f[u][0];
}
int wmax(int u, int v) {
  int ret = 0, l = lca(u, v);

  for (int i = 16; i >= 0; --i) {
    if (!anc(f[u][i], v) || f[u][i] == l) {
      ret = max(ret, g[u][i]);
      u = f[u][i];
    }
  }
  for (int i = 16; i >= 0; --i) {
    if (!anc(f[v][i], u) || f[v][i] == l) {
      ret = max(ret, g[v][i]);
      v = f[v][i];
    }
  }

  return ret;
}
int binary_jump(int u, int v) {
  int ret = 1e9 + 1;

  for (int i = 16; i >= 0; --i) if (!anc(f[u][i], v)) {
    ret = min(ret, dp[u][i]);
    u = f[u][i];
  }
  for (int i = 16; i >= 0; --i) if (!anc(f[v][i], u)) {
    ret = min(ret, dp[v][i]);
    v = f[v][i];
  }

  return ret;
}

vector<int> co;
bool sub1;
int answers1;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N; m = M;
  sub1 = 1;
  for (int i = 0; i < m; ++i) {
    int u = U[i], v = V[i], w = W[i];
    co.push_back(w);
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
    if (ad[u].size() > 2 || ad[v].size() > 2) sub1 = 0;
    answers1 = max(answers1, w);
  }
  if (m == n - 1) {
    dfs(0);
    dpout[0] = 1e9 + 1;
    dfs_out(0);
  }


  sort(co.begin(), co.end());
  co.resize(unique(co.begin(), co.end()) - co.begin());

}

bool dd[N];
int special;
bool dfs1(int u, int pre, int cw) {
  if (u == special) return 1;
  bool ret = 0;
  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre || w > cw) continue;
    if (!dd[v]) {
      dd[v] = 1;
      ret |= dfs1(v, u, cw);
    }
  }
  return ret;
}

bool dfs2(int u, int pre, int cw) {
  int cnt = pre != -1;
  bool ret = 0;
  map<int, int> d;
  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre || w > cw) continue;
    if (dd[v] && !d[v]) return 1;
    if (!dd[v]) {
      dd[v] = d[v] = 1;
      cnt += 1;
      ret |= dfs2(v, u, cw);
    }
  }

  return (cnt > 2 || ret);
}

int getMinimumFuelCapacity(int X, int Y) {
  if (sub1 && m != n - 1) return answers1;
  if (m == n - 1) {
    if (sub1) return -1;
    int answer = 1e9 + 1;
    int l = lca(X, Y);
    if (anc(Y, X)) swap(X, Y);
    if (!anc(X, Y)) answer = min(answer, dpin[X]);
    answer = min({answer, dpin[Y], binary_jump(X, Y)});


    int maxw = wmax(X, Y);
    if (X != l && Y != l) {

      if (ad[l].size() >= 3) {
        for (int i = 16; i >= 0; --i) if (!anc(f[X][i], Y)) X = f[X][i];
        for (int i = 16; i >= 0; --i) if (!anc(f[Y][i], X)) Y = f[Y][i];
        int it = 0;
        while (ad[l][it].first == X || ad[l][it].first == Y) it += 1;
        answer = min(answer, ad[l][it].second);
      }

    } else {

      answer = min({answer, dpout[Y]});
    }

    answer = max(answer, maxw);

    return answer;
  }


  int l = 0, r = co.size() - 1;
  int answer = -1;
  special = Y;
  while (l <= r) {
    int mid = l + r >> 1;

    bool ret = 1;
    memset(dd, 0, sizeof dd); ret &= dfs1(X, -1, co[mid]);
    memset(dd, 0, sizeof dd); ret &= dfs2(X, -1, co[mid]);

    if (ret) r = mid - 1, answer = co[mid];
    else l = mid + 1;
  }

  return answer;
}

#ifdef LOCAL
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  int n, m; cin >> n >> m;
  vector<int> U(m), V(m), W(m);
  for (int i = 0; i < m; ++i) cin >> U[i] >> V[i] >> W[i];
  init(n, m, U, V, W);

  int q; cin >> q;
  for (int i = 1; i <= q; ++i) {
    int X, Y; cin >> X >> Y;
    cout << getMinimumFuelCapacity(X, Y) << '\n';
  }


}
#endif // LOCAL

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

swap.cpp: In function 'bool dfs2(int, int, int)':
swap.cpp:190:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  190 |       dd[v] = d[v] = 1;
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:236:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  236 |     int mid = l + r >> 1;
      |               ~~^~~

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