제출 #1125094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125094		ntdaccode	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	4138 ms	170096 KiB

reconstruction

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 2e6 + 10;
const int N = 5e2 + 10;
const int mod = 1e9 + 7;

int n, m, q, x[M];
struct node
{
  int u, v, w, idx;
  node() : u(0), v(0), w(0), idx(0) {}
  node(int u,int v,int w,int idx) : u(u), v(v), w(w), idx(idx) {}
  bool operator < (const node &rhs) {return w < rhs.w; }
  friend ostream& operator << (ostream &os, node rhs) {
    return os << "(" << rhs.u << ", " << rhs.v << ", " << rhs.w << ")" <<  "\n";
  }
};

node edge[100010];

int id[N];
int finded(int u) {
  return id[u] < 0 ? u : id[u] = finded(id[u]);
}

bool unioned(int u,int v)
{
  u = finded(u);
  v = finded(v);
  if(u == v) return false;
  if(id[u] > id[v]) swap(u,v);
  id[u] += id[v];
  id[v] = u;
  return true;
}

int par[N], mi[N], num[N], tail[N], cnt;
vector<ii> ke[N];

void dfs(int u,int p)
{
  num[u] = ++cnt;
  for(ii tmp : ke[u]) {
    int v = tmp.first, w = tmp.second;
      if(v == p) continue;
      //cout << v << " " << u << " " << w << "\n";
      par[v] = u;
      mi[v] = w;
      dfs(v,u);
  }
  tail[u] = cnt;
}

bool anc(int u,int v)
{
  return num[u] <= num[v] && tail[u] >= tail[v];
}

void make_tree(int pre_idx,int cur_idx,vector<int> &pre)
{
  if(pre_idx != 0) {
    vector<int> cur;
    for(int v : pre) if(v != pre_idx) cur.pb(v);
    cur.pb(cur_idx);
    swap(pre,cur);
  }
  else pre.pb(cur_idx);
//  for(int v : pre) cout << v << " ";
//  cout << endl;
  cnt = 0;
  for(int i = 1;i <= n; i++)
  {
    ke[i].clear();
    num[i] = tail[i] = 0;
  }
  for(int idx : pre) {
    int u = edge[idx].u, v = edge[idx].v;
    ke[u].pb({v,idx});
    ke[v].pb({u,idx});
  }
  for(int i = 1;i <= n; i++) {
      if(!num[i]) dfs(i,0);
  }

}

///
int nxt[M];

int get(int u,int v) {
  int res = 0;
  while(!anc(u,v)) {
      res = max(res, mi[u]);
      u = par[u];
  }
  while(!anc(v,u)) {
    res = max(res, mi[v]);
    v = par[v];
  }
  return res;
}

void calculate_nxt()
{
  for(int i = 1;i <= m; i++) nxt[i] = -1;
  for(int i = 1;i <= n; i++) id[i] = -1;
  vector<int> store;
  for(int i = m; i != 0; i--) {
      if(unioned(edge[i].u,edge[i].v)) {
        make_tree(0,i,store);
        //cout << i << "\n";
      }
      else {
        nxt[i] = get(edge[i].u,edge[i].v);
        //cout << i << " " << nxt[i] << "\n";
        make_tree(nxt[i],i,store);
      }
  }
  //for(int i = 1;i <= m; i++) cerr << i << " " << nxt[i] << "\n";
}

vector<int> Q[M];
vector<int> change[M];
vector<int> rrh;
///
void roi_rac_hoa()
{
  // rrh
  for(int i = 1;i <= m; i++) {
    if(nxt[i] != -1) {
      rrh.pb((edge[i].w + edge[nxt[i]].w)/2);
    }
  }
  for(int i = 1;i <= q; i++) rrh.pb(x[i]);
  sort(rrh.begin(), rrh.end());
  rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
  for(int i = 1;i <= m; i++) {
    if(nxt[i] != -1) {
      int val = (edge[i].w + edge[nxt[i]].w)/2;
      val = lower_bound(rrh.begin(), rrh.end(), val) - rrh.begin() + 1;
      change[val].pb(i);
    }
  }
  for(int i = 1;i <= q; i++) {
    int val = lower_bound(rrh.begin(), rrh.end(), x[i]) - rrh.begin() + 1;
    Q[val].pb(i);
  }

}
///
//void make_unioned(vector<int> &pre,int val)
//{
//  vector<int> cur;
//  for(int i = 1;i <= n; i++) id[i] = -1;
//  reverse(pre.begin(),pre.end());
//  for(int idx : pre) {
//      if(unioned(edge[idx].u, edge[idx].v)) {
//          cur.pb(idx);
//      }
//  }
//  reverse(cur.begin(),cur.end());
////  if(val == 7) {
////    for(int v : cur) cout << v << " ";
////  }
//  swap(pre,cur);
//
//}


int ans[M];
void solve()
{
  multiset<int> store;
  cnt = n;
  for(int i = 1;i <= n; i++) id[i] = -1;

  for(int i = m;i != 0; i--) {
      if(unioned(edge[i].u,edge[i].v)) {
        cnt--;
        store.insert(i);
      }
      if(cnt == 1) break;
  }


  int sz = rrh.size();
  for(int i = sz;i != 0; i--) {
      sort(change[i].begin(), change[i].end(),greater<int> ());
      for(int idx : change[i]) {
         // cout << idx << " " << nxt[idx] << "\n";
        store.insert(idx);
        store.erase(store.find(nxt[idx]));
      }

      for(int idx : Q[i]) {
          for(int v : store) {
              ans[idx] += abs(x[idx] - edge[v].w);
              //cout << edge[v] ;
          }
      }
  }

}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  if(fopen("1.inp","r")) {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }

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

  cin >> n >> m;
  for(int i = 1;i <= m; i++) {
    cin >> edge[i].u >> edge[i].v >> edge[i].w;
    edge[i].idx = i;
  }
  sort(edge + 1,edge + m + 1);
  cin >> q;
  for(int i = 1;i <= q; i++) cin >> x[i];
  calculate_nxt();
  roi_rac_hoa();
  solve();

  for(int i = 1;i <= q; i++) cout << ans[i] << "\n";


}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:220:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:221:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:226:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:227:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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