Submission #529836

#	Time	Username	Problem	Language	Result	Execution time	Memory
529836		cadmiumsky	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4046 ms	14152 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[nmax], query[nmax];
int w[nmax];

namespace BFS {
  priority_queue<pair<int, int> > que;
  void bfs() {
    if(que.empty())
      return;
    int t, node;
    tie(t, node) = que.top();
    que.pop();
    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.push({costs[node], 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;
  int sol[nmax], temp[nmax];
  void apply(int n) {
    sort(events.begin(), events.end());
    DSU::init(n);
    for(auto [c, x, y] : events) {
      if(x < 0)
        DSU::unite(-x, y);
      else { 
        if(DSU::query(x, (x ^ other[y])))
          sol[y] = temp[y];
        //cout << "? " << y <<'\t' << c << '\n';
      }
    }
  }
  void cbin(int n, int m, int q) {
    for(int i = 0; i < q; i++)
      sol[i] = -1;
    for(int i = 29; i >= 0; i--) {
      events.resize(0);
      for(int j = 0; j < q; j++)
        temp[j] = sol[j] + (1 << i), events.push_back({-temp[j], query[j].first, j});
      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});
      apply(n);
      //cout << "================\n";
    }
  }
}
namespace PRINT {
  void print(int q) {
    for(int i = 0; i < q; i++)
      cout << CBIN::sol[i] << '\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.push({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:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [c, x, y] : events) {
      |              ^

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