답안 #915191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915191	2024-01-23T13:04:20 Z	duckindog	자매 도시 (APIO20_swap)	C++14	0 / 100	2000 ms	30368 KB

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;
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});

  }
  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 = bool(pre);
  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) {

  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, 0, co[mid]);
    memset(dd, 0, sizeof dd); ret &= dfs2(X, 0, 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:56:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   56 |       dd[v] = d[v] = 1;
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2904 KB	Output is correct
5	Correct	2 ms	2908 KB	Output is correct
6	Correct	3 ms	2908 KB	Output is correct
7	Correct	2 ms	2908 KB	Output is correct
8	Correct	3 ms	3164 KB	Output is correct
9	Correct	129 ms	25328 KB	Output is correct
10	Correct	201 ms	28032 KB	Output is correct
11	Correct	224 ms	28780 KB	Output is correct
12	Correct	316 ms	28220 KB	Output is correct
13	Correct	748 ms	30368 KB	Output is correct
14	Execution timed out	2009 ms	25456 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Execution timed out	2031 ms	16176 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2904 KB	Output is correct
5	Correct	2 ms	2908 KB	Output is correct
6	Correct	3 ms	2908 KB	Output is correct
7	Correct	2 ms	2908 KB	Output is correct
8	Correct	3 ms	3164 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	2 ms	2972 KB	Output is correct
11	Correct	2 ms	2908 KB	Output is correct
12	Correct	2 ms	2908 KB	Output is correct
13	Correct	2 ms	2908 KB	Output is correct
14	Correct	2 ms	2908 KB	Output is correct
15	Correct	3 ms	2908 KB	Output is correct
16	Correct	3 ms	2904 KB	Output is correct
17	Correct	3 ms	3060 KB	Output is correct
18	Correct	2 ms	2908 KB	Output is correct
19	Correct	3 ms	2908 KB	Output is correct
20	Correct	2 ms	2908 KB	Output is correct
21	Correct	3 ms	2908 KB	Output is correct
22	Incorrect	3 ms	2908 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	2 ms	2904 KB	Output is correct
6	Correct	2 ms	2908 KB	Output is correct
7	Correct	3 ms	2908 KB	Output is correct
8	Correct	2 ms	2908 KB	Output is correct
9	Correct	3 ms	3164 KB	Output is correct
10	Correct	129 ms	25328 KB	Output is correct
11	Correct	201 ms	28032 KB	Output is correct
12	Correct	224 ms	28780 KB	Output is correct
13	Correct	316 ms	28220 KB	Output is correct
14	Correct	748 ms	30368 KB	Output is correct
15	Correct	2 ms	2972 KB	Output is correct
16	Correct	2 ms	2908 KB	Output is correct
17	Correct	2 ms	2908 KB	Output is correct
18	Correct	2 ms	2908 KB	Output is correct
19	Correct	2 ms	2908 KB	Output is correct
20	Correct	3 ms	2908 KB	Output is correct
21	Correct	3 ms	2904 KB	Output is correct
22	Correct	3 ms	3060 KB	Output is correct
23	Correct	2 ms	2908 KB	Output is correct
24	Correct	3 ms	2908 KB	Output is correct
25	Correct	2 ms	2908 KB	Output is correct
26	Correct	3 ms	2908 KB	Output is correct
27	Incorrect	3 ms	2908 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2904 KB	Output is correct
5	Correct	2 ms	2908 KB	Output is correct
6	Correct	3 ms	2908 KB	Output is correct
7	Correct	2 ms	2908 KB	Output is correct
8	Correct	3 ms	3164 KB	Output is correct
9	Correct	129 ms	25328 KB	Output is correct
10	Correct	201 ms	28032 KB	Output is correct
11	Correct	224 ms	28780 KB	Output is correct
12	Correct	316 ms	28220 KB	Output is correct
13	Correct	748 ms	30368 KB	Output is correct
14	Execution timed out	2009 ms	25456 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	2 ms	2904 KB	Output is correct
6	Correct	2 ms	2908 KB	Output is correct
7	Correct	3 ms	2908 KB	Output is correct
8	Correct	2 ms	2908 KB	Output is correct
9	Correct	3 ms	3164 KB	Output is correct
10	Correct	129 ms	25328 KB	Output is correct
11	Correct	201 ms	28032 KB	Output is correct
12	Correct	224 ms	28780 KB	Output is correct
13	Correct	316 ms	28220 KB	Output is correct
14	Correct	748 ms	30368 KB	Output is correct
15	Execution timed out	2009 ms	25456 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

답안 #915191

Compilation message

Subtask #1 0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0