Submission #257042

#	Time	Username	Problem	Language	Result	Execution time	Memory
257042		Bruteforceman	Aesthetic (NOI20_aesthetic)	C++11	35 / 100	2098 ms	75000 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
const int logn = 19;
const long long inf = 1e16;
int anc[logn + 1][maxn];
int l[maxn], r[maxn], w[maxn];
vector <int> g[maxn], t[maxn];
long long ans[maxn];
int dep[maxn];
int n, m;

struct data {
  long long dist;
  int node;
  data (long long dist, int node) : dist(dist), node(node) {}
  data () {}
  bool operator < (data d) const {
    return dist > d.dist;
  }
};

vector <long long> dijstra(int root) {
  priority_queue <data> Q;

  vector <long long> dist (n, inf);
  Q.emplace(0, root);
  dist[root] = 0;
  while(!Q.empty()) {
    int node = Q.top().node;
    long long var = Q.top().dist;
    Q.pop();
    if(var != dist[node]) continue;
    for(int e : g[node]) {
      int x = l[e] ^ r[e] ^ node;
      if(w[e] + dist[node] < dist[x]) {
        dist[x] = w[e] + dist[node];
        Q.emplace(dist[x], x);
      }
    }
  }
  return dist;
}
void dfs(int x) {
  for(int i = 1; i <= logn; i++) {
    anc[i][x] = anc[i - 1][anc[i - 1][x]];
  }
  for(int i : t[x]) {
    dep[i] = 1 + dep[x];
    anc[0][i] = x;
    dfs(i);
  }
}
int lca(int x, int y) {
  if(dep[x] > dep[y]) swap(x, y);
  for(int i = logn; i >= 0; i--) {
    if(dep[y] - (1 << i) >= dep[x]) {
      y = anc[i][y];
    }
  }
  if(x == y) return x;
  for(int i = logn; i >= 0; i--) {
    if(anc[i][x] != anc[i][y]) {
      x = anc[i][x];
      y = anc[i][y];
    }
  }
  return anc[0][x];
}
int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++) {
    scanf("%d %d %d", &l[i], &r[i], &w[i]);
    l[i] -= 1;
    r[i] -= 1;
    g[l[i]].push_back(i);
    g[r[i]].push_back(i);
  }
  vector <long long> forward = dijstra(0);
  vector <int> par (n);
  for(int i = 1; i < n; i++) {
    for(int e : g[i]) {
      int x = l[e] ^ r[e] ^ i;
      if(forward[x] + w[e] == forward[i]) {
        par[i] = e;
        t[x].push_back(i);
        break;
      }
    }
  }
  dfs(0);
  vector <long long> backward = dijstra(n - 1);
  int cur = n - 1;
  vector <bool> onPath (m);
  vector <int> id (n);
  while(cur != 0) {
    int e = par[cur];
    onPath[e] = true;
    cur = anc[0][cur];
    id[dep[cur]] = e;
  }
  for(int i = 0; i < m; i++) ans[i] = inf;
  vector <vector <pair <int, int>>> cont (n); 
  for(int i = 0; i < m; i++) {
    if(onPath[i]) continue;
    ans[i] = forward[n - 1];
    int p = lca(l[i], n - 1);
    int q = lca(r[i], n - 1);
    if(dep[p] > dep[q])  {
      swap(p, q);
      swap(l[i], r[i]);
    }
    long long cost = w[i] + forward[l[i]] + backward[r[i]];
    for(int x = dep[p]; x < dep[q]; x++) {
      ans[id[x]] = min(ans[id[x]], cost);
    }
    // cont[dep[p]].emplace_back(cost, 1);
    // cont[dep[q]].emplace_back(cost, -1);
  }
  /* multiset <long long> bst;
  for(int i = 0; i < dep[n - 1]; i++) {
    for(auto j : cont[i]) {
      if(j.second == 1) bst.insert(j.first);
      else bst.erase(bst.find(j.first));
    }
    ans[id[i]] = bst.empty() ? inf : *bst.begin();
    cout << id[i] << ' ';
  }
  */
  int mx = w[m - 1];
  long long res = 0;
  for(int i = m - 2; i >= 0; i--) {
    long long p = forward[l[i]] + mx + w[i] + backward[r[i]];
    long long q = forward[r[i]] + mx + w[i] + backward[l[i]];
    res = max(res, min({ans[i], p, q}));
    mx = max(mx, w[i]);
  }
  printf("%lld\n", res);
  return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
Aesthetic.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l[i], &r[i], &w[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27