Submission #1122146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122146		vjudge1	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	270 ms	53076 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

const int N = 3e5 + 5;

int n, m;
int head[N], pr[N], pos[N], tin[N], sz[N], ind[N], res[N], s[4 * N];
bool inside[N], vis[N];
pair<int, int> dat[N];
vector<pair<int, int>> g[N];

void dfs(int u) {
  sz[u] = 1;
  for (auto x : g[u]) {
    int v, id;
    tie(v, id) = x;
    g[v].erase(find(g[v].begin(), g[v].end(), make_pair(u, id)));
    pr[v] = u;
    ind[v] = id;
    dfs(v);
    sz[u] += sz[v];
  }
}

int order;

void hld(int u, int h) {
  head[u] = h;
  pos[tin[u] = ++order] = u;
  if (sz[u] > 1) {
    auto x = (*max_element(g[u].begin(), g[u].end(), [&](auto x, auto y) {
      return sz[x.first] < sz[y.first];
    })).first;
    hld(x, h);
    for (auto v : g[u]) {
      if (v.first ^ x) {
        hld(v.first, v.first);
      }
    }
  }  
}

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = ind[pos[l]];
    return;
  }
  int m = (l + r) / 2;
  bld(id * 2, l, m);
  bld(id * 2 + 1, m + 1, r);
  s[id] = min(s[id * 2], s[id * 2 + 1]);
}

void upd(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = N;
    return;
  }
  int m = (l + r) / 2;
  i <= m ? upd(i, id * 2, l, m) : upd(i, id * 2 + 1, m + 1, r);
  s[id] = min(s[id * 2], s[id * 2 + 1]);
}

int qry(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int m = (l + r) / 2;
  if (v <= m) {
    return qry(u, v, id * 2, l, m);
  }
  if (m < u) {
    return qry(u, v, id * 2 + 1, m + 1, r);
  }
  return min(qry(u, v, id * 2, l, m), qry(u, v, id * 2 + 1, m + 1, r));
}

int get(int u, int v) {
  int res = N;
  for (; head[u] ^ head[v]; u = pr[head[u]]) {
    if (sz[head[u]] > sz[head[v]]) {
      swap(u, v);
    }
    res = min(res, qry(tin[head[u]], tin[u]));
  }
  if (tin[u] > tin[v]) {
    swap(u, v);
  }
  if (tin[u] + 1 <= tin[v]) {
    res = min(res, qry(tin[u] + 1, tin[v]));
  }
  return res;
}

int ans;

void DFS(int id) {
  vis[id] = 1;
  int u, v;
  tie(u, v) = dat[id];
  if (!inside[id]) {
    int nxt = N;
    while ((nxt = get(u, v)) ^ N) {
      DFS(nxt);
    }
  } else {
    upd(max(tin[u], tin[v]));
  }
  res[id] = ++ans;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  file("A");
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    dat[i] = {u, v};
  }
  for (int i = 1; i < n; ++i) {
    int j; cin >> j;
    inside[j] = 1;
    int u, v;
    tie(u, v) = dat[j];
    g[u].push_back({v, j});
    g[v].push_back({u, j});
  }
  ind[1] = N;
  dfs(1);
  hld(1, 1);
  bld();
  for (int i = 1; i <= m; ++i) {
    if (!vis[i]) {
      DFS(i);
    }
    cout << res[i] << " ";
  }
  return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:11:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:123:3: note: in expansion of macro 'file'
  123 |   file("A");
      |   ^~~~
riggedroads.cpp:11:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:123:3: note: in expansion of macro 'file'
  123 |   file("A");
      |   ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32