Submission #284039

#	Time	Username	Problem	Language	Result	Execution time	Memory
284039		milleniumEeee	Highway Tolls (IOI18_highway)	C++14	0 / 100	16 ms	3072 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define ll long long
#define fr first
#define sc second

using namespace std;

const int N = 90004;
vector <pii> g[N];
int x[N], y[N];
int n, m, a, b;
int S, T;
vector <int> w;

void create(vector <int> &path) {
  for (int i = 0; i < m; i++) {
    w[i] = 1;
  }
  for (int edge : path) {
    assert(edge < m);
    w[edge] = 0;
  }
}

long long before = 1e18;

struct Edge {
  int id;
  int to;
  ll cost;
  Edge (int id_, int to_, ll cost_) {
    id = id_, to = to_;
  }
  Edge () {
    
  }
  bool operator < (const Edge &other) {
    return cost < other.cost;
  }
};

void dfs(int v, int par, vector <int> &path) {
  vector <Edge> vec; // cost / vertex
  for (pii el : g[v]) {
    if (el.sc == par) {
      continue;
    }
    path.push_back(el.fr);
    create(path);
    vec.push_back(Edge(el.fr, el.sc, ask(w)));
    path.pop_back();
  }
  sort (vec.begin(), vec.end());
  if (vec.empty() || vec[0].cost == before) {
    S = 0, T = v;
  } else {
    path.push_back(vec[0].id);
    before = vec[0].cost;
    dfs(vec[0].to, v, path);
  }
}

void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
  n = NN;
  m = U.size();
  a = A;
  b = B;
  w.resize(m);
  for (int i = 0; i < m; i++) {
    x[i] = U[i];
    y[i] = V[i];
    g[x[i]].push_back({i, y[i]});
    g[y[i]].push_back({i, x[i]});
  }
  vector <int> path = {};
  dfs(0, -1, path);
  answer(S, T);
}

/*

10
9
4
9
4
1
4 6
9 5
5 0
8 2
1 7
7 4
4 2
2 9
3 9

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31