Submission #257094

#	Time	Username	Problem	Language	Result	Execution time	Memory
257094		Bruteforceman	Aesthetic (NOI20_aesthetic)	C++11	51 / 100	1414 ms	82260 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];
}
long long prop[maxn * 4];
void update(int x, int y, long long val, int c = 1, int b = 0, int e = n) {
  if(x <= b && e <= y) {
    prop[c] = min(prop[c], val);
    return ;
  }
  if(y < b || e < x) return ;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  update(x, y, val, l, b, m);
  update(x, y, val, r, m + 1, e);
}
long long get(int x, int c = 1, int b = 0, int e = n) {
  if(b == e) return prop[c];
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) return min(prop[c], get(x, l, b, m));
  else return min(prop[c], get(x, r, m + 1, e));
}
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);
  }
  for(int i = 0; i <= 4 * (n + 1); i++) prop[i] = inf;
  vector <long long> forward = dijstra(0);
  vector <long long> backward = dijstra(n - 1);

  vector <int> par (n);
  vector <pair <long long, int>> ord;
  for(int i = 0; i < n; i++) ord.emplace_back(forward[i], i);
  sort(ord.begin(), ord.end());
  vector <bool> done (n, false);
  for(auto y : ord) {
    int i = y.second;
    for(int e : g[i]) {
      int x = l[e] ^ r[e] ^ i;
      if(forward[x] + w[e] == forward[i] && done[x]) {
        par[i] = e;
        t[x].push_back(i);
        break;
      }
    }
    done[i] = true;
  }
  dfs(0);
  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;
  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);
    }
    long long cost = min(w[i] + forward[l[i]] + backward[r[i]], 
        w[i] + forward[r[i]] + backward[l[i]]);
    if(dep[p] < dep[q]) {
      update(dep[p], dep[q] - 1, cost);
    }
  }
  for(int i = 0; i < dep[n - 1]; i++) {
    ans[id[i]] = get(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:92: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:94: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: 16 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27