제출 #1039733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039733		NeroZein	통행료 (IOI18_highway)	C++17	18 / 100	249 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std; 
 
const int N = 1e5 + 5; 
 
int n, m, a, b;
vector<int> g[N]; 
int pe[N], dep[N];
long long min_dist;
vector<int> iu, iv;
int idd, pr[N], in[N], out[N];
 
void dfs(int v, int p) {
  in[v] = idd++; 
  for (int i : g[v]) {
    int u = iu[i] ^ iv[i] ^ v; 
    if (u == p) {
      continue; 
    }
    pe[u] = i; 
    pr[u] = v; 
    dep[u] = dep[v] + 1; 
    //cout << "u, i, dep: " << u << ' ' << i << ' ' << dep[u] << endl;
    dfs(u, v); 
  }
  out[v] = idd - 1; 
}
 
void dfs2(int v, int p, vector<int>& w) {
  for (int i : g[v]) {
    int u = iu[i] ^ iv[i] ^ v;
    if (u == p) {
      continue; 
    }
    w[i] = true; 
    dfs2(u, v, w); 
  }
}
 
bool isParent(int v, int u) {
  return in[v] <= in[u] && out[v] >= out[u];
}
 
int figure(vector<int>& candidates) {
  //bool deb = false; 
  //vector<int> o = {3, 4};
  //if (candidates == o) {
    //deb = true; 
  //}
  while (candidates.size() > 1) {
    vector<int> w(m, 0); 
    int s = (int) candidates.size();
    int mid = s / 2; 
    for (int i = 0; i < mid; ++i) {
      int v = candidates[i]; 
      w[pe[v]] = true; 
    }
    long long tmp = ask(w); 
    vector<int> new_candidates; 
    if (tmp == min_dist) {//lca is not among first mid elements
      for (int i = mid; i < s; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    } else {
      for (int i = 0; i < mid; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    }
    candidates = new_candidates;
  }
  return candidates[0];
}
 
void find_pair(int n_, vector<int> U, vector<int> V, int a_, int b_) {
  iu = U, iv = V;
  n = n_; a = a_; b = b_;
  m = (int) U.size(); 
  for (int i = 0; i < m; ++i) {
    g[U[i]].push_back(i);
    g[V[i]].push_back(i);
  }
  dfs(0, 0); 
  vector<int> w(m, 0); 
  min_dist = ask(w); 
  //lca depth is the largest depth such that if all nodes with depth <= this depth parent edges were heavy the orginal cost is not affected
  int l = 0, r = n - 1; 
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r + 1) >> 1;
    for (int i = 1; i < n; ++i) {
      if (dep[i] <= mid) {
        w[pe[i]] = 1; 
      }
    }
    long long tmp = ask(w);
    if (tmp == min_dist) {
      l = mid;
    } else {
      r = mid - 1; 
    }
  }
  int lca_depth = l; 
  //cerr << "DEP: " << lca_depth << endl; 
  vector<int> candidates; 
  for (int i = 0; i < n; ++i) {
    if (dep[i] == lca_depth) {
      candidates.push_back(i); 
    }
  }
  while (candidates.size() > 1) {
    int s = (int) candidates.size();
    int mid = s / 2; 
    fill(w.begin(), w.end(), 0); 
    for (int i = 0; i < mid; ++i) {
      int v = candidates[i];
      dfs2(v, pr[v], w); 
    }
    long long tmp = ask(w);
    vector<int> new_candidates; 
    if (tmp == min_dist) {//lca is not among first mid elements
      for (int i = mid; i < s; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    } else {
      for (int i = 0; i < mid; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    }
    candidates = new_candidates;
  }
  int lca = candidates[0];
  cerr << "LCA: " << lca << '\n'; 
  l = 0, r = (int) g[lca].size() - 1; 
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; ++i) {
      int u = lca ^ iu[g[lca][i]] ^ iv[g[lca][i]];
      w[g[lca][i]] = true; 
      dfs2(u, lca, w); 
    }
    long long tmp = ask(w);
    if (tmp != min_dist) {
      r = mid;
    } else {
      l = mid + 1; 
    }
  }
  int ind = g[lca][l];
  //cerr << "ind: " << ind << endl; 
  int first_son_s = iu[ind] ^ iv[ind] ^ lca;
  cerr << "firstson: " << first_son_s << endl; 
  fill(w.begin(), w.end(), 0); 
  dfs2(first_son_s, lca, w); 
  int depS = dep[first_son_s] + (ask(w) - min_dist) / (b - a); 
  candidates.clear();
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depS && isParent(first_son_s, i)) {
      candidates.push_back(i); 
    }
  }
  int s = figure(candidates);  
  cerr << "S: " << s << endl; 
  //reverse(g[lca].begin(), g[lca].end()); 
  l = l + 1, r = (int) g[lca].size();
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; ++i) {
      int u = lca ^ iu[g[lca][i]] ^ iv[g[lca][i]];
      //cerr << "i, u: " << i << ' ' << u << endl; 
      w[g[lca][i]] = true; 
      dfs2(u, lca, w); 
    }
    long long tmp = ask(w);
    if (tmp != min_dist) {
      r = mid;
    } else {
      l = mid + 1; 
    }
  }
  if (l == (int) g[lca].size()) {
    answer(lca, s);
    return; 
  }
  ind = g[lca][l];
  //cerr << "ind: " << ind << endl; 
  int first_son_t = iu[ind] ^ iv[ind] ^ lca; 
  //cerr << "lca, first_son_t: " << lca << ' ' << first_son_t << endl; 
  fill(w.begin(), w.end(), 0); 
  dfs2(first_son_t, lca, w); 
  //int depT = dep[first_son_t] + (ask(w) - min_dist) / (b - a); 
  int depT = min_dist / a - dep[s] + dep[lca] * 2;
  //cerr << "min_dist / a: " << min_dist / a << endl; 
  candidates.clear();
  cerr << "s, first_son_t: " << s << ' ' << first_son_t << endl; 
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depT && isParent(first_son_t, i)) {
      candidates.push_back(i); 
      cerr << "I: " << i << endl; 
    } 
  }
  //assert(candidates.size() == 0); 
  int t = figure(candidates); 
  cerr << "T: " << t << endl; 
  answer(s, t); 
}

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