제출 #1158139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158139		lopkus	Reconstruction Project (JOI22_reconstruction)	C++20	3 / 100	35 ms	6800 KiB

reconstruction

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 501;

vector<pair<int, pair<int,int>>> left_edges[N];
vector<pair<int, pair<int,int>>> right_edges[N];


vector<pair<int, pair<int,int>>> tmp;

struct DSU{
    int P[N];
    int siz[N];
    void add(){
        for(int i = 1; i < N; i++) {
          P[i] = i;
          siz[i] = 1;
        }
        return;
    }
    int parent(int x){
        if(x==P[x])return x;
        return P[x]=parent(P[x]);
    }
    void connect(int u,int v){
        u=parent(u);
        v=parent(v);
        if(u!=v){
            if(siz[u]<siz[v])swap(u,v);
            P[v]=u;
            siz[u]+=siz[v];
        }
        return;
    }
    int same(int u, int v) {
        return parent(u) == parent(v);
    }
    void to_clear() {
      for(int i = 0; i < N; i++) {
        P[i] = siz[i] = 0;
      }
    }
}dsu;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, pair<int,int>>> edges(m);
  for(int i = 0; i < m; i++) {
    cin >> edges[i].second.first >> edges[i].second.second >> edges[i].first;
    if(edges[i].second.first > edges[i].second.second) {
      swap(edges[i].second.first, edges[i].second.second);
    }
  }
  sort(edges.begin(), edges.end());
  int q;
  cin >> q;
  set<pair<int,int>> st;
  map<pair<int,int>, int> latest_value;
  for(int i = 0; i < m; i++) {
    latest_value[{edges[i].second.first, edges[i].second.second}] = edges[i].first;
    st.insert({edges[i].second.first, edges[i].second.second});
    int k = 501;
    while(k-- && st.size()) {
      auto it = st.end();
      pair<int,int> x = (*(--it));
      int u = x.first;
      int v = x.second;
      int w = latest_value[{u, v}];
      left_edges[i].push_back({w, {u, v}});
      st.erase(it);
    }
    for(auto it : left_edges[i]) {
      st.insert({it.second.first, it.second.second});
    }
  }
  st.clear();
  latest_value.clear();
  for(int i = m - 1; i >= 0; i--) {
    latest_value[{edges[i].second.first, edges[i].second.second}] = edges[i].first;
    st.insert({edges[i].second.first, edges[i].second.second});
    int k = 501;
    while(k-- && st.size()) {
      auto it = st.end();
      pair<int,int> x = (*(--it));
      int u = x.first;
      int v = x.second;
      int w = latest_value[{u, v}];
      right_edges[i].push_back({w, {u, v}});
      st.erase(it);
    }
    for(auto it : right_edges[i]) {
      st.insert({it.second.first, it.second.second});
    }
  }
  while(q--) {
    dsu.add();
    int x;
    cin >> x;
    vector<pair<int, pair<int,int>>> useful_edges;
    sort(useful_edges.begin(), useful_edges.end());
    int l = 0, r = m - 1, pos = - 1;
    while(l <= r) {
      int mid = (l + r) / 2;
      if(edges[mid].first <= x) {
        l = mid + 1;
        pos = mid;
      }
      else {
        r = mid - 1;
      }
    }
    if(pos == - 1) {
      pos = 0;
    }
    else {
      if(pos != m - 1) {
        if(abs(edges[pos + 1].first - x) < abs(edges[pos].first - x)) {
          pos += 1;
        }
      }
    }
    for(int i = 0; i < (int)left_edges[pos].size(); i++) {
      int u = left_edges[pos][i].second.first;
      int v = left_edges[pos][i].second.second;
      int w = left_edges[pos][i].first;
      useful_edges.push_back({abs(x - w), {u, v}});
    }
    for(int i = 0; i < right_edges[pos].size(); i++) {
      int u = right_edges[pos][i].second.first;
      int v = right_edges[pos][i].second.second;
      int w = right_edges[pos][i].first;
      useful_edges.push_back({abs(x - w), {u, v}});
    }
    sort(useful_edges.begin(), useful_edges.end());
    int ans = 0;
    for(int i = 0; i < useful_edges.size(); i++) {
      int u = useful_edges[i].second.first;
      int v = useful_edges[i].second.second;
      int w = useful_edges[i].first;
      if(!dsu.same(u, v)) {
        ans += w;
        dsu.connect(u, v);
      }
    }
    cout << ans << "\n";
    dsu.to_clear();
  }
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23