Submission #529849

#	Time	Username	Problem	Language	Result	Execution time	Memory
529849		cadmiumsky	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1800 ms	37536 KiB

plan

#include <bits/stdc++.h>
//#error fa inituri
using namespace std;
const int nmax = 1e5 + 5;
const int mmax = 5e5 + 5;
int costs[nmax], other[nmax];;
vector<int> g[nmax];
pair<int,int> edge[mmax], query[nmax];
int w[mmax];

namespace BFS {
  priority_queue<pair<int, int> > que;
  void bfs() {
    if(que.empty())
      return;
    int t, node;
    tie(t, node) = que.top();
    t *= -1;
    que.pop();
    if(t != costs[node])
      return bfs();
    for(auto x : g[node]) {
      int c = node ^ edge[x].first ^ edge[x].second;
      if(costs[c] > w[x] + costs[node]) {
        costs[c] = costs[node] + w[x];
        que.emplace(-costs[c], c);
      }
    }
    bfs();
  }
}
namespace DSU {
  int dsu[nmax];
  void init(int n) {
    for(int i = 1; i <= n; i++) 
      dsu[i] = i;
  }
  int father(int x) {
    return (dsu[x] == x? x : father(dsu[x] = father(dsu[dsu[x]])));
  }
  bool query(int a, int b) {
    a = father(a);
    b = father(b);
    //cout << "? " << a << ' ' << b<<' ' ;
    if(a != b)
      return 0;
    return 1;
  }
  void unite(int a, int b) {
    a = father(a);
    b = father(b);
    dsu[a] = b;
    //cout << "! " << a << ' ' << b << ' ';
  }
};
namespace CBIN {
  vector<tuple<int, int, int> > events;
  vector<tuple<int, int, int> > ev;
  int sol[nmax], temp[nmax];
  void apply(int n) {
    sort(events.begin(), events.end());
    DSU::init(n);
    int ptr = 0;
    int x, y, t;
    for(auto [cost, l, r] : events) {
      while(ptr < ev.size() && get<0>(ev[ptr]) <= cost) {
        tie(t, x, y) = ev[ptr];
         if(DSU::query(x, (x ^ other[y])))
          sol[y] = temp[y];
        ptr++;
      }
      DSU::unite(-l, r);
    }
  }
  void cbin(int n, int m, int q) {
    for(int j = 0; j < m; j++)
        events.push_back({-min(costs[edge[j].first], costs[edge[j].second])
                        , -edge[j].first, edge[j].second});
    sort(events.begin(), events.end());
    for(int i = 0; i < q; i++)
      sol[i] = -1;
    ev.resize(q);
    for(int i = 29; i >= 0; i--) {
      for(int j = 0; j < q; j++)
        temp[j] = sol[j] + (1 << i), ev[j] = {-temp[j], query[j].first, j};
      sort(ev.begin(), ev.end());
      apply(n);
      //cout << "================\n";
    }
  }
}
namespace PRINT {
  void print(int q) {
    for(int i = 0; i < q; i++)
      cout << CBIN::sol[i] + 1 << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k, q;
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> edge[i].first >> edge[i].second >> w[i];
    g[edge[i].first].push_back(i);
    g[edge[i].second].push_back(i);
  }
  fill(costs, costs + n + 1, 1e9 + 5);
  cin >> k;
  for(int i = 0, x; i < k; i++) {
    cin >> x;
    costs[x] = 0;
    BFS::que.emplace(0, x);
  }
  cin >> q;
  for(int i = 0; i < q; i++)
    cin >> query[i].first >> query[i].second,
    other[i] = query[i].first ^ query[i].second;
  BFS::bfs();
  CBIN::cbin(n, m, q);
  PRINT::print(q);
  return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void CBIN::apply(int)':
plan.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto [cost, l, r] : events) {
      |              ^
plan.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |       while(ptr < ev.size() && get<0>(ev[ptr]) <= cost) {
      |             ~~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46