Submission #1125093

#TimeUsernameProblemLanguageResultExecution timeMemory
1125093ntdaccodeReconstruction Project (JOI22_reconstruction)C++17
42 / 100
2586 ms146232 KiB
#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 = 1e6 + 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[M]; 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[M], 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); // //} bool dd[M]; 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"; }

Compilation message (stderr)

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:219:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
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.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:225:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...