제출 #1160934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160934		aeg	Rigged Roads (NOI19_riggedroads)	C++20	0 / 100	121 ms	15500 KiB

riggedroads

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

struct dsu {
  vector<int> vec;
  int finddsu(int s) {
    if(vec[s] < 0) return s;
    return vec[s] = finddsu(vec[s]);
  }
  void unify(int a, int b) {
    a = finddsu(a), b = finddsu(b);
    if(a == b) return;
    if(vec[a] < vec[b]) swap(a, b);
    vec[b] += vec[a];
    vec[a] = b;
  }
  dsu(int n) : vec(n, -1) {}
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, e;
  cin >> n >> e;
  vector<pair<int, int>> adj(e, {0, 0});
  for(auto &[x, y]: adj) {
    cin >> x >> y;
    x--;
    y--;
  }
  set<int> s;
  for (int i = 1; i < n; i++) {
    int j;
    cin >> j;
    j --;
    s.insert(j);
  }
  int val = 1, nonval = n;
  vector<int> ans(e);
  dsu a(e);
  for (int i = 0; i < e; i++) {
    if (s.count(i)) {
      ans[i] = val++;
      a.unify(adj[i].first, adj[i].second);
      continue;
    }
    if (a.finddsu(adj[i].first) == a.finddsu(adj[i].second)) {
      ans[i] = val++;
      nonval++;
      continue;
    } else {
      ans[i] = nonval++;
    }
  }
}

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