Submission #1122203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122203		fryingduc	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	365 ms	57160 KiB

riggedroads

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
int n, a[maxn], m;
vector<pair<int, int>> g[maxn];
int sz[maxn], par[maxn], h[maxn];
int head[maxn], pos[maxn], rev[maxn];
int cur_pos;
int eu[maxn], ev[maxn];
int mark[maxn];

void pre_dfs(int u, int prev) {
  sz[u] = 1;
  for(auto e:g[u]) {
    int v = e.first, id = e.second;
    if(v == prev) continue;
    par[v] = u;
    h[v] = h[u] + 1;
    a[v] = id;
    pre_dfs(v, u);
    sz[u] += sz[v];
  }
}
void hld(int u, int prev) {
  if(!head[u]) {
    head[u] = u;
  }
  pos[u] = ++cur_pos;
  rev[cur_pos] = u;
  int big_child = -1;
  for(auto e:g[u]) {
    int v = e.first;
    if(v == prev) continue;
    if(big_child == -1 || sz[big_child] < sz[v]) big_child = v;
  }
  if(big_child != -1) {
    head[big_child] = head[u];
    hld(big_child, u);
  }
  for(auto e:g[u]) {
    int v = e.first;
    if(v == prev || v == big_child) continue;
    hld(v, u);
  }
}
vector<pair<int, int>> intervals;
void collect(int u, int v) {
  intervals.clear();
  while(head[u] != head[v]) {
    if(h[head[u]] > h[head[v]]) {
      swap(u, v);
    }
    intervals.emplace_back(pos[head[v]], pos[v]);
    v = par[head[v]];
  }
  if(h[u] > h[v]) swap(u, v);
  if(pos[u] + 1 <= pos[v]) intervals.emplace_back(pos[u] + 1, pos[v]);
}
void solve() {
  cin >> n >> m;
  for(int i = 1; i <= m; ++i) {
    cin >> eu[i] >> ev[i];
  }
  for(int i = 1; i < n; ++i) { 
    int id; cin >> id;
    g[eu[id]].emplace_back(ev[id], id);
    g[ev[id]].emplace_back(eu[id], id);    
  }
  pre_dfs(1, 0);
  par[1] = 1;
  hld(1, 0);
  
  int total = 0;
  set<int> s;
  for(int i = 1; i <= n; ++i) {
    s.insert(i);
  }
  for(int i = 1; i <= m; ++i) {
    collect(eu[i], ev[i]);
    if((int)intervals.size() == 1 and intervals[0].first == intervals[0].second) {
      if(!mark[intervals[0].first]) {
        mark[intervals[0].first] = ++total;
        s.erase(intervals[0].first);
      }
      cout << mark[intervals[0].first] << " ";
      continue;
    }
    vector<int> wait;
    for(auto cand:intervals) {
      while(true) {
        auto it = s.lower_bound(cand.first);
        if(it == s.end() || *it > cand.second) break;
        wait.push_back(*it);
        s.erase(it);
      }
    }
    sort(wait.begin(), wait.end(), [&](const int &x, const int &y) -> bool {
      return a[rev[x]] < a[rev[y]];
    });
    for(auto j:wait) {
      mark[j] = ++total;
    }
    cout << ++total << ' ';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• 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