제출 #915684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915684		duckindog	자매 도시 (APIO20_swap)	C++14	43 / 100	1093 ms	31708 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];

vector<int> co;
bool sub1 = 1, sub2 = 1;
int maxw = 0;

int par[N];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N; m = M;
  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});
    maxw = max(maxw, w);
    if (ad[u].size() > 2 || ad[v].size() > 2) sub1 = 0;
    if (u) {
      sub2 = 0;
      par[v] = w;
    }
  }
  if (sub2) {
    using pii = pair<int, int>;
    sort(ad[0].begin(), ad[0].end(), [&] (pii a, pii b) {
      return make_pair(a.second, a.first) > make_pair(b.second, b.first);
    });
  }

  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 -1;
  if (sub1 && m == n) return maxw;

  if (sub2) {
    int it = 0;
    while (ad[0][it].first == X || ad[0][it].first == Y) it += 1;
    return max({ad[0][it].second, par[X], par[Y]});
  }

  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:72:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   72 |       dd[v] = d[v] = 1;
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:95:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     int mid = l + r >> 1;
      |               ~~^~~

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