Submission #701751

#	Time	Username	Problem	Language	Result	Execution time	Memory
701751		dattranxxx	Swapping Cities (APIO20_swap)	C++11	Compilation error	0 ms	0 KiB

swap

#include <bits/stdc++.h>
//#include "swap.h"
using namespace std;
using ll = long long;

const int N = 3e5 + 5;

struct Edge {
  int u, v, w;
  Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
  bool operator < (const Edge& e) const {
    return w < e.w;
  }
} ed[N];

int n, m;

int lin[N], deg[N], ok[N], val[N];

int find(int i) {
  if (i == lin[i]) {
    return i;
  }
  return lin[i] = find(lin[i]);
}

vector<int> adj[N];

int unite(int u, int v, int w) {
  u = find(u); v = find(v);
  
  n++;
  lin[u] = lin[v] = lin[n] = n;
  val[n] = w;
  
  adj[n].emplace_back(u);
  ok[n] |= ok[u];

  if (u != v) {
    adj[n].emplace_back(v);
    ok[n] |= ok[v];
  } else {
    ok[n] = 1;
  }
  
  return n;
}

int dep[N], par[N][19];
void dfs(int u) {
  for (int v : adj[u]) {
    dep[v] = dep[u] + 1;
    par[v][0] = u; 
    for (int i = 1; i <= 18; ++i) {
      par[v][i] = par[par[v][i - 1]][i - 1];
    }
    dfs(v);
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  
  for (int i = 18; ~i; --i) {
    if (dep[par[u][i]] >= dep[v]) {
      u = par[u][i];
    }
  }
  
  if (u == v) {
    return u;
  }
  
  for (int i = 18; ~i; --i) {
    if (par[u][i] != par[v][i]) {
      u = par[u][i]; v = par[v][i];
    }
  }
  
  return par[u][0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  for (int i = 1; i <= m; ++i) {
    int u = U[i - 1] + 1, v = V[i - 1] + 1, w = W[i - 1];
    ed[i] = {u, v, w};
  }
  
  sort(ed + 1, ed + m + 1);
  
  for (int i = 1; i <= n; ++i) {
    lin[i] = i;
  }
  
  for (int i = 1; i <= m; ++i) {
    deg[ed[i].u]++; deg[ed[i].v]++;
    int id = unite(ed[i].u, ed[i].v, ed[i].w);
    ok[id] |= deg[ed[i].u] >= 3 || deg[ed[i].v] >= 3;
  }
  
  int root = find(1);
  dfs(root);
  
}

int getMinimumFuelCapacity(int X, int Y) {
  int u = X + 1, v = Y + 1;

  int z = lca(u, v);
  if (ok[z]) {
    return val[z];
  }
  
  for (int i = 18; ~i; --i) {
    if (par[z][i] && !ok[par[z][i]]) {
      z = par[z][i];
    }
  }
  z = par[z][0];
  
  return ok[z] ? val[z] : -1;
}


int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    scanf("%d", &U[i]);
  }
  for (int i = 0; i < M; ++i) {
    scanf("%d", &V[i]);
  }
  for (int i = 0; i < M; ++i) {
    scanf("%d", &W[i]);
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    scanf("%d %d ", &X[i], &Y[i]);
  }

  init(N, M, U, V, W);
  
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d", &U[i]);
      |     ~~~~~^~~~~~~~~~~~~
swap.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     scanf("%d", &V[i]);
      |     ~~~~~^~~~~~~~~~~~~
swap.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     scanf("%d", &W[i]);
      |     ~~~~~^~~~~~~~~~~~~
swap.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%d %d ", &X[i], &Y[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cctF7wIt.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccTMkCNu.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status