Submission #502843

#	Time	Username	Problem	Language	Result	Execution time	Memory
502843		Pety	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1016 ms	58632 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1e5 + 2;

int n, m, dist[N], viz[N], k, nodes[N], x[N], y[N], l[N], r[N];
bool connected[N];
bool found[N];
int p[N], sz[N];
vector<pair<int, int> >G[N];
priority_queue<pair<int, int>>pq;

struct qry {
  int x, y, i;
};

vector<qry>queries[N];

bool cmp (int x, int y) {
  return dist[x] > dist[y];
}

int find (int x) {
  if (p[x] == x)
    return x;
  return p[x] = find(p[x]);
}

void Union (int x, int y) {
  x = find(x);
  y = find(y);
  if (x != y) {
    if (sz[x] > sz[y]) {
      p[y] = x;
      sz[x] += sz[y];
    }
    else {
      p[x] = y;
      sz[y] += sz[x];
    }
  }
}


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    G[x].push_back({y, z});
    G[y].push_back({x, z});
  }  
  for (int i = 1; i <= n; i++) {
    dist[i] = 1e9;
  }
  cin >> k;
  while (k--) {
    int x;
    cin >> x;
    dist[x] = 0;
    pq.push({dist[x], x});
  }
  while (pq.size()) {
    auto p = pq.top();
    pq.pop();
    if (-p.first != dist[p.second])
      continue;
    for (auto it : G[p.second]) {
      if (it.second - p.first < dist[it.first]) {
        dist[it.first] = it.second - p.first;
        pq.push({-dist[it.first], it.first});
      }
    }
  }
  for (int i = 1; i <= n; i++)
    nodes[i] = i;
  sort(nodes + 1, nodes + n + 1, cmp);
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> x[i] >> y[i];
    l[i] = 1;
    r[i]= n;
  }
  while (1) {
    bool ok = 0;
    for (int i = 1; i <= q; i++) {
      if (l[i] <= r[i]) {
        ok = 1;
        queries[(l[i] + r[i]) / 2].push_back({x[i], y[i], i});
      }
    }
    if (!ok)
      break;
    for (int i = 1; i <= n; i++) {
      p[i] = i;
      sz[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
      for (auto it : G[nodes[i]])
        if (found[it.first])
          Union(it.first, nodes[i]);
      for (auto it : queries[i]) {
        connected[it.i] = (find(it.x) == find(it.y));
      }
      found[nodes[i]] = 1;
    }
    for (int i = 1; i <= q; i++)  
      if (l[i] <= r[i]) {
        if (connected[i])
          r[i] = (l[i] + r[i]) / 2 - 1;
        else
          l[i] = (l[i] + r[i]) / 2 + 1;
      }
    for (int i = 1; i <= n; i++) {
      connected[i] = 0;
      found[i] = 0;
      queries[i].clear();
    }
  }
  for (int i = 1; i <= q; i++)
    cout << dist[nodes[l[i]]] << "\n";
    
  return 0;
}

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