Submission #802717

#	Time	Username	Problem	Language	Result	Execution time	Memory
802717		radaiosm7	Swapping Cities (APIO20_swap)	C++11	6 / 100	124 ms	20464 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int i, mx;
bool visited[100005];
vector<int> adj[100005];
bool cycle;

void dfs(int x, int p=-1) {
  visited[x] = true;

  for (auto y : adj[x]) {
    if (y == p) continue;
    if (visited[y]) cycle = true;
    else dfs(y, x);
  }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  for (i=0; i < M; ++i) {
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
  }

  cycle = false;
  dfs(1);
  mx = -1;
  for (i=0; i < M; ++i) mx = max(mx, W[i]);
}

int getMinimumFuelCapacity(int X, int Y) {
  return (cycle ? mx : -1);
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27