제출 #1122636

#제출 시각아이디문제언어결과실행 시간메모리
1122636ntdaccodeReconstruction Project (JOI22_reconstruction)C++17
14 / 100
2045 ms64056 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 = 1e3 + 10; const int mod = 1e9 + 7; int n, m, q, uu[M], vv[M], ww[M]; namespace sub2 { int id[M]; 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(v == u) return false; if(id[u] > id[v]) swap(u,v); id[u] += id[v]; id[v] = u; return true; } void solve() { while(q--) { int x; cin >> x; vector<tp> edge; int kq = 0; for(int i = 1;i <= m; i++) edge.pb({abs(ww[i] - x),uu[i],vv[i]}); sort(edge.begin(),edge.end()); for(int i = 1;i <= n; i++) id[i] = -1; int v,u,w; for(int i = 0;i <= edge.size() - 1; i++) { tie(w,u,v) = edge[i]; if(unioned(u,v)) kq += w; } cout << kq << "\n"; } } } namespace sub3 { vector<int> Q[M]; int idx[M], ans[M]; ii xx[M]; void solve() { for(int i = 1;i <= m; i++) { Q[uu[i]].pb(ww[i]); idx[uu[i]] = 0; } for(int i = 1;i <= n - 1; i++) sort(Q[i].begin(),Q[i].end()); for(int i = 1;i <= q; i++) { cin >> xx[i].first; xx[i].second = i; } sort(xx + 1,xx + q + 1); for(int i = 1;i <= q; i++) { int kq = 0; int val = xx[i].first; for(int j = 1;j <= n - 1; j++) { int sz = Q[j].size(); //cout << abs(Q[j][idx[j]] - val) << " " << abs(Q[j][idx[j] + 1] - val) << "\n"; while(idx[j] < sz - 1 && abs(Q[j][idx[j]] - val) >= abs(Q[j][idx[j] + 1] - val)) idx[j]++; if(idx[j] <= sz - 1) kq += abs(Q[j][idx[j]] - val); // cout << //cout << Q[j][idx[j]] << " "; } ans[xx[i].second] = kq; } for(int i = 1;i <= q;i ++) cout << ans[i] << "\n"; } } 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.ans","w",stdout); } #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> m ; bool ok = 0; for(int i = 1;i <= m; i++) { cin >> uu[i] >> vv[i] >> ww[i]; } cin >> q; if(q <= 10 ) sub2 :: solve(); else sub3 :: solve(); }

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

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     freopen("1.ans","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:105:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     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...