Submission #915037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915037	2024-01-23T08:33:14 Z	duckindog	Swapping Cities (APIO20_swap)	C++14	Compilation error	0 ms	0 KB

swap

#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;

}
#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;
      |               ~~^~~
swap.cpp: At global scope:
swap.cpp:85:11: error: redefinition of 'const int N'
   85 | const int N = 1e5 + 10,
      |           ^
swap.cpp:7:11: note: 'const int N' previously defined here
    7 | const int N = 1e5 + 10,
      |           ^
swap.cpp:86:11: error: redefinition of 'const int M'
   86 |           M = 1e3 + 10;
      |           ^
swap.cpp:8:11: note: 'const int M' previously defined here
    8 |           M = 1e3 + 10;
      |           ^
swap.cpp:87:5: error: redefinition of 'int n'
   87 | int n, m;
      |     ^
swap.cpp:9:5: note: 'int n' previously declared here
    9 | int n, m;
      |     ^
swap.cpp:87:8: error: redefinition of 'int m'
   87 | int n, m;
      |        ^
swap.cpp:9:8: note: 'int m' previously declared here
    9 | int n, m;
      |        ^
swap.cpp:88:24: error: redefinition of 'std::vector<std::pair<int, int> > ad [100010]'
   88 | vector<pair<int, int>> ad[N];
      |                        ^~
swap.cpp:10:24: note: 'std::vector<std::pair<int, int> > ad [100010]' previously declared here
   10 | vector<pair<int, int>> ad[N];
      |                        ^~
swap.cpp:90:6: error: redefinition of 'bool chain'
   90 | bool chain;
      |      ^~~~~
swap.cpp:12:6: note: 'bool chain' previously declared here
   12 | bool chain;
      |      ^~~~~
swap.cpp:91:13: error: redefinition of 'std::vector<int> co'
   91 | vector<int> co;
      |             ^~
swap.cpp:13:13: note: 'std::vector<int> co' previously declared here
   13 | vector<int> co;
      |             ^~
swap.cpp:92:6: error: redefinition of 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
   92 | void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
      |      ^~~~
swap.cpp:14:6: note: 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
   14 | void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
      |      ^~~~
swap.cpp:108:6: error: redefinition of 'bool dd [100010]'
  108 | bool dd[N];
      |      ^~
swap.cpp:30:6: note: 'bool dd [100010]' previously declared here
   30 | bool dd[N];
      |      ^~
swap.cpp:109:5: error: redefinition of 'int special'
  109 | int special;
      |     ^~~~~~~
swap.cpp:31:5: note: 'int special' previously declared here
   31 | int special;
      |     ^~~~~~~
swap.cpp:110:6: error: redefinition of 'bool dfs1(int, int, int)'
  110 | bool dfs1(int u, int pre, int cw) {
      |      ^~~~
swap.cpp:32:6: note: 'bool dfs1(int, int, int)' previously defined here
   32 | bool dfs1(int u, int pre, int cw) {
      |      ^~~~
swap.cpp:124:6: error: redefinition of 'bool dfs2(int, int, int)'
  124 | bool dfs2(int u, int pre, int cw) {
      |      ^~~~
swap.cpp:46:6: note: 'bool dfs2(int, int, int)' previously defined here
   46 | bool dfs2(int u, int pre, int cw) {
      |      ^~~~
swap.cpp:138:5: error: redefinition of 'int getMinimumFuelCapacity(int, int)'
  138 | int getMinimumFuelCapacity(int X, int Y) {
      |     ^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:60:5: note: 'int getMinimumFuelCapacity(int, int)' previously defined here
   60 | int getMinimumFuelCapacity(int X, int Y) {
      |     ^~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:145:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |     int mid = l + r >> 1;
      |               ~~^~~