oj.uz

답안 #915688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915688 2024-01-24T14:36:53 Z duckindog 자매 도시 (APIO20_swap) C++14
43 / 100
 1673 ms 30144 KB 
#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 (m != n - 1) sub2 = 0;

  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;
    int answer = max(par[X], par[Y]);
    while (ad[0][it].first == X || ad[0][it].first == Y) it += 1;
    answer = max(answer, ad[0][it].second);

    if (!X || !Y) {
      it += 1;
      while (ad[0][it].first == X || ad[0][it].first == Y) it += 1;
      answer = max(answer, ad[0][it].second);
    }

    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

Compilation message

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3120 KB Output is correct
9 Correct 30 ms 8896 KB Output is correct
10 Correct 38 ms 10092 KB Output is correct
11 Correct 36 ms 9936 KB Output is correct
12 Correct 38 ms 10184 KB Output is correct
13 Correct 41 ms 10292 KB Output is correct
14 Correct 33 ms 9136 KB Output is correct
15 Correct 77 ms 12768 KB Output is correct
16 Correct 76 ms 12664 KB Output is correct
17 Correct 81 ms 13360 KB Output is correct
18 Correct 88 ms 13544 KB Output is correct
19 Correct 41 ms 8756 KB Output is correct
20 Correct 87 ms 14080 KB Output is correct
21 Correct 81 ms 14132 KB Output is correct
22 Correct 92 ms 14900 KB Output is correct
23 Correct 83 ms 14768 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Incorrect 82 ms 13280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3120 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 2 ms 3160 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 2 ms 3164 KB Output is correct
14 Correct 3 ms 3160 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct
16 Correct 2 ms 3164 KB Output is correct
17 Correct 3 ms 3420 KB Output is correct
18 Correct 3 ms 3164 KB Output is correct
19 Correct 3 ms 3332 KB Output is correct
20 Correct 2 ms 3376 KB Output is correct
21 Correct 3 ms 3164 KB Output is correct
22 Correct 3 ms 3120 KB Output is correct
23 Correct 3 ms 3164 KB Output is correct
24 Correct 4 ms 3420 KB Output is correct
25 Correct 5 ms 3164 KB Output is correct
26 Correct 3 ms 3420 KB Output is correct
27 Correct 3 ms 3164 KB Output is correct
28 Correct 4 ms 3420 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 1 ms 3120 KB Output is correct
10 Correct 30 ms 8896 KB Output is correct
11 Correct 38 ms 10092 KB Output is correct
12 Correct 36 ms 9936 KB Output is correct
13 Correct 38 ms 10184 KB Output is correct
14 Correct 41 ms 10292 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct
16 Correct 2 ms 3160 KB Output is correct
17 Correct 2 ms 3164 KB Output is correct
18 Correct 2 ms 3164 KB Output is correct
19 Correct 3 ms 3160 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 2 ms 3164 KB Output is correct
22 Correct 3 ms 3420 KB Output is correct
23 Correct 3 ms 3164 KB Output is correct
24 Correct 3 ms 3332 KB Output is correct
25 Correct 2 ms 3376 KB Output is correct
26 Correct 3 ms 3164 KB Output is correct
27 Correct 3 ms 3120 KB Output is correct
28 Correct 3 ms 3164 KB Output is correct
29 Correct 4 ms 3420 KB Output is correct
30 Correct 5 ms 3164 KB Output is correct
31 Correct 3 ms 3420 KB Output is correct
32 Correct 3 ms 3164 KB Output is correct
33 Correct 4 ms 3420 KB Output is correct
34 Correct 11 ms 4444 KB Output is correct
35 Correct 194 ms 25456 KB Output is correct
36 Correct 152 ms 18380 KB Output is correct
37 Correct 147 ms 12356 KB Output is correct
38 Correct 266 ms 10556 KB Output is correct
39 Correct 174 ms 9840 KB Output is correct
40 Correct 272 ms 9676 KB Output is correct
41 Correct 201 ms 20288 KB Output is correct
42 Correct 225 ms 22836 KB Output is correct
43 Correct 555 ms 23440 KB Output is correct
44 Correct 288 ms 10696 KB Output is correct
45 Correct 695 ms 18232 KB Output is correct
46 Correct 310 ms 20820 KB Output is correct
47 Correct 321 ms 10288 KB Output is correct
48 Correct 409 ms 10940 KB Output is correct
49 Correct 92 ms 13860 KB Output is correct
50 Correct 124 ms 11208 KB Output is correct
51 Correct 576 ms 16036 KB Output is correct
52 Correct 1118 ms 23552 KB Output is correct
53 Correct 311 ms 15600 KB Output is correct
54 Correct 1673 ms 30144 KB Output is correct
55 Correct 423 ms 18316 KB Output is correct
56 Correct 1195 ms 20936 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 1 ms 3120 KB Output is correct
9 Correct 30 ms 8896 KB Output is correct
10 Correct 38 ms 10092 KB Output is correct
11 Correct 36 ms 9936 KB Output is correct
12 Correct 38 ms 10184 KB Output is correct
13 Correct 41 ms 10292 KB Output is correct
14 Correct 33 ms 9136 KB Output is correct
15 Correct 77 ms 12768 KB Output is correct
16 Correct 76 ms 12664 KB Output is correct
17 Correct 81 ms 13360 KB Output is correct
18 Correct 88 ms 13544 KB Output is correct
19 Incorrect 82 ms 13280 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 1 ms 3120 KB Output is correct
10 Correct 30 ms 8896 KB Output is correct
11 Correct 38 ms 10092 KB Output is correct
12 Correct 36 ms 9936 KB Output is correct
13 Correct 38 ms 10184 KB Output is correct
14 Correct 41 ms 10292 KB Output is correct
15 Correct 33 ms 9136 KB Output is correct
16 Correct 77 ms 12768 KB Output is correct
17 Correct 76 ms 12664 KB Output is correct
18 Correct 81 ms 13360 KB Output is correct
19 Correct 88 ms 13544 KB Output is correct
20 Incorrect 82 ms 13280 KB Output isn't correct
21 Halted 0 ms 0 KB -