oj.uz

답안 #915040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915040 2024-01-23T08:34:49 Z duckindog 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 12900 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 = -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;

}

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 2996 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 2 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 2648 KB Output is correct
9 Correct 30 ms 8532 KB Output is correct
10 Correct 39 ms 9676 KB Output is correct
11 Correct 36 ms 9604 KB Output is correct
12 Correct 38 ms 9932 KB Output is correct
13 Correct 41 ms 9928 KB Output is correct
14 Correct 35 ms 8944 KB Output is correct
15 Correct 78 ms 12372 KB Output is correct
16 Correct 79 ms 12408 KB Output is correct
17 Correct 80 ms 12900 KB Output is correct
18 Correct 80 ms 12804 KB Output is correct
19 Incorrect 51 ms 7164 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 2996 KB Output is correct
3 Execution timed out 2061 ms 12560 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 2996 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 2 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 2648 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 ms 2908 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 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2996 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 2 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 2648 KB Output is correct
10 Correct 30 ms 8532 KB Output is correct
11 Correct 39 ms 9676 KB Output is correct
12 Correct 36 ms 9604 KB Output is correct
13 Correct 38 ms 9932 KB Output is correct
14 Correct 41 ms 9928 KB Output is correct
15 Correct 2 ms 2908 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 2996 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 2 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 2648 KB Output is correct
9 Correct 30 ms 8532 KB Output is correct
10 Correct 39 ms 9676 KB Output is correct
11 Correct 36 ms 9604 KB Output is correct
12 Correct 38 ms 9932 KB Output is correct
13 Correct 41 ms 9928 KB Output is correct
14 Correct 35 ms 8944 KB Output is correct
15 Correct 78 ms 12372 KB Output is correct
16 Correct 79 ms 12408 KB Output is correct
17 Correct 80 ms 12900 KB Output is correct
18 Correct 80 ms 12804 KB Output is correct
19 Execution timed out 2061 ms 12560 KB Time limit exceeded
20 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 2652 KB Output is correct
3 Correct 1 ms 2996 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 2 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 2648 KB Output is correct
10 Correct 30 ms 8532 KB Output is correct
11 Correct 39 ms 9676 KB Output is correct
12 Correct 36 ms 9604 KB Output is correct
13 Correct 38 ms 9932 KB Output is correct
14 Correct 41 ms 9928 KB Output is correct
15 Correct 35 ms 8944 KB Output is correct
16 Correct 78 ms 12372 KB Output is correct
17 Correct 79 ms 12408 KB Output is correct
18 Correct 80 ms 12900 KB Output is correct
19 Correct 80 ms 12804 KB Output is correct
20 Execution timed out 2061 ms 12560 KB Time limit exceeded
21 Halted 0 ms 0 KB -