oj.uz

답안 #915038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915038 2024-01-23T08:33:33 Z duckindog 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 14684 KB 
#include "swap.h"

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10,
          M = 1e3 + 10;
int n, m;
vector<pair<int, int>> ad[N];

bool chain;
vector<int> co;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N; m = M;
  chain = 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) chain = 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 = 0;
  bool ret = 0;
  for (auto duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    if (v == pre || w > cw) continue;
    if (dd[v]) return 1;
    dd[v] = 1;
    cnt += 1;
    ret |= dfs2(v, u, cw);
  }
  return (cnt > 2 || ret);
}

int getMinimumFuelCapacity(int X, int Y) {
  if (chain) return -1;

  int l = 0, r = co.size() - 1;
  int answer = 0;
  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;

}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 30 ms 9052 KB Output is correct
10 Correct 38 ms 10360 KB Output is correct
11 Correct 43 ms 10416 KB Output is correct
12 Correct 38 ms 10764 KB Output is correct
13 Correct 38 ms 10684 KB Output is correct
14 Correct 34 ms 9336 KB Output is correct
15 Correct 79 ms 14452 KB Output is correct
16 Correct 103 ms 14344 KB Output is correct
17 Correct 86 ms 14684 KB Output is correct
18 Correct 91 ms 14640 KB Output is correct
19 Incorrect 42 ms 8292 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2808 KB Output is correct
11 Incorrect 2 ms 2908 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 30 ms 9052 KB Output is correct
11 Correct 38 ms 10360 KB Output is correct
12 Correct 43 ms 10416 KB Output is correct
13 Correct 38 ms 10764 KB Output is correct
14 Correct 38 ms 10684 KB Output is correct
15 Correct 2 ms 2808 KB Output is correct
16 Incorrect 2 ms 2908 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 30 ms 9052 KB Output is correct
10 Correct 38 ms 10360 KB Output is correct
11 Correct 43 ms 10416 KB Output is correct
12 Correct 38 ms 10764 KB Output is correct
13 Correct 38 ms 10684 KB Output is correct
14 Correct 34 ms 9336 KB Output is correct
15 Correct 79 ms 14452 KB Output is correct
16 Correct 103 ms 14344 KB Output is correct
17 Correct 86 ms 14684 KB Output is correct
18 Correct 91 ms 14640 KB Output is correct
19 Execution timed out 2027 ms 14184 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 30 ms 9052 KB Output is correct
11 Correct 38 ms 10360 KB Output is correct
12 Correct 43 ms 10416 KB Output is correct
13 Correct 38 ms 10764 KB Output is correct
14 Correct 38 ms 10684 KB Output is correct
15 Correct 34 ms 9336 KB Output is correct
16 Correct 79 ms 14452 KB Output is correct
17 Correct 103 ms 14344 KB Output is correct
18 Correct 86 ms 14684 KB Output is correct
19 Correct 91 ms 14640 KB Output is correct
20 Execution timed out 2027 ms 14184 KB Time limit exceeded
21 Halted 0 ms 0 KB -