Submission #672884

#	Time	Username	Problem	Language	Result	Execution time	Memory
672884		YENGOYAN	Evacuation plan (IZhO18_plan)	C++17	0 / 100	146 ms	16128 KiB

plan

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;

int n, m, k, q;
vector<vector<pair<int, ll>>> gp;
vector<ll> g, mind, par, sizes;
vector<pair<ll, int>> vp;

int get(int u) {
  if (u == par[u])
    return u;
  return par[u] = get(par[u]);
}

void union_sets(int u, int v) {
  int a = get(u), b = get(v);
  if (a == b)
    return;
  if (sizes[a] < sizes[b])
    swap(a, b);
  par[b] = a;
  sizes[a] += sizes[b];
}

bool check(int x, int y, ll W) {
  sizes = par = vector<ll>(n, 1);
  for (int i = 0; i < n; ++i)
    par[i] = i;
  for (int i = 0; i < n; ++i) {
    for (pair<int, ll> &v : gp[i]) {
      if (min(mind[i], mind[v.first]) >= W)
        union_sets(i, v.first);
    }
  }
  return get(x) == get(y);
}

void solve() {
  // what we can do, I don't have any idea
  //
  cin >> n >> m;
  gp = vector<vector<pair<int, ll>>>(n);
  mind = vector<ll>(n, 1e18);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    gp[--u].push_back({--v, w});
    gp[v].push_back({u, w});
  }
  cin >> k;
  g = vector<ll>(k);
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
      pq;
  for (int i = 0; i < k; ++i)
    cin >> g[i], --g[i], pq.push({0, g[i]}), mind[g[i]] = 0;
  while (pq.size()) {
    pair<ll, int> p = pq.top();
    pq.pop();
    ll d = p.first, u = p.second;
    if (mind[u] < d)
      continue;
    for (pair<int, ll> v : gp[u]) {
      if (mind[v.first] > mind[u] + v.second) {
        mind[v.first] = mind[u] + v.second;
        pq.push({mind[v.first], v.first});
      }
    }
  }
  // it's not maximum spanning tree
  // but it is so similar to it
  // we need to check for each query
  // whether it is to possible to get from X to Y
  // only using roads only with length smaller than W
  // what we will do? 
  cin >> q;
  vector<pair<pair<pair<int, int>, pair<int, int>>, int>> vp;
  int id = 0;
  vector<pair<int, int>> qry;
  while (q--) {
    int s, t;
    cin >> s >> t;
    --s, --t;
    qry.push_back({s, t});
    if(mind[s] > mind[t]) vp.push_back({{{mind[s], mind[t]}, {s, t}}, id++});
    else vp.push_back({{{mind[t], mind[s]}, {s, t}}, id++});
  }
  sort(vp.begin(), vp.end());
  map<pair<int, int>, ll> answers;
  // u, v, answer is atmost min(mind[u], mind[v]);   
  // how to answer for query u, v
  // RTTD
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
}

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