제출 #1314676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314676		joshjuice	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	157 ms	55476 KiB

riggedroads

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

#define int long long
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define all(a) a.begin(), a.end()
#define srtvc(a) sort(all(a))
#define bcsrtvc(a) sort(all(a), greater<__typeof__(a[0])>())
#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define fr first
#define sc second
#define pq priority_queue
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vc vector
#define dq deque
#define stk stack
#define umap unordered_map
#define sz(a) a.size()
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
#define setval(arr, x) memset(arr, x, sizeof(arr))

template<typename T>
using vv = vc<vc<T>>;

const int MAX = 3e5+1;

vc<pii> g[MAX];
int par[MAX], id[MAX], d[MAX], p[MAX];
vc<int> ids;

void dfs(int v) {
  for (auto [ch, i] : g[v]) {
    if (ch == par[v]) continue;
    d[ch] = d[v]+1;
    id[ch] = i;
    par[ch] = v;
    dfs(ch);
  }
}

int find(int x) {
  return (x == p[x] ? x : (p[x] = find(p[x])));
}

int unite(int x, int y, int i) {
  x = find(x);
  if (x == y) return x;
  ids.pb(i);
  p[y] = x;
  return x;
}

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  vc<iii> e;
  rep(i, 0, m) {
    int u, v;
    cin >> u >> v;
    e.pb({u, v, i});
  }
  vc<bool> r(m, 0);
  rep(i, 1, n) {
    int x;
    cin >> x;
    r[--x] = 1;
  }
  int x;
  for (auto [u, v, i] : e) {
    if (r[i]) {
      g[u].eb(v, i);
      g[v].eb(u, i);
      x = u;
    }
  }
  dfs(x);
  rep(i, 1, n+1) p[i] = i;
  vc<int> ans(m, -1);
  int cnt = 0;
  for (auto [u, v, i] : e) {
    //used hence use smallest available weight
    if (r[i]) {
      if (ans[i] == -1) {
        ans[i] = ++cnt;
        if (d[u] < d[v]) swap(u, v);
        unite(par[u], u, 0);
        ids.clear();
      }
      continue;
    }
    u = find(u);
    v = find(v);
    while (u != v) {
      if (d[u] < d[v]) swap(u, v);
      u = unite(par[u], u, id[u]);
    }
    srtvc(ids);
    //push their weight away for road to be able to use the smallest weight
    for (int x : ids) ans[x] = ++cnt;
    ans[i] = ++cnt;
    ids.clear();
  }
  rep(i, 0, m) cout << ans[i] << ' ';
}

• 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