제출 #235327

#제출 시각아이디문제언어결과실행 시간메모리
235327wwddConstruction of Highway (JOI18_construction)C++14
0 / 100
6 ms512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pl; typedef vector<pl> vpl; typedef vector<int> vi; typedef vector<vi> vvi; const int MN = 100100; vvi g; vector<pl> eg; vi po,par; vi sub; vi col,cop; vvi hl; vector<vpl> hac; vi mac; class ST { private: int n; vector<ll> st; public: ST(int _n) {n = _n;st.assign(2*n,0);} void up(int p, ll val) { p += n; st[p] += val; while(p > 1) { st[p>>1] = st[p]+st[p^1]; p >>= 1; } } ll get(int l, int r) { l += n;r += n; ll res = 0; for(;l<r;l>>=1,r>>=1) { if(l&1) { res += st[l];l++; } if(r&1) {--r; res += st[r]; } } return res; } }; int dfa(int u, int p) { int res = 1; par[u] = p; for(int i=0;i<g[u].size();i++) { int v = g[u][i]; if(v == p) {continue;} int da = dfa(v,u); if(mac[u] == -1 || da > sub[mac[u]]) { mac[u] = v; } res += da; } return sub[u] = res; } void dfb(int u, int p, int co) { cop[u] = hl[co].size(); col[u] = co; hl[co].push_back(u); for(int i=0;i<g[u].size();i++) { int v = g[u][i]; if(v == p) {continue;} if(v == mac[u]) { dfb(v,u,co); } else { int nuc = hl.size(); hl.emplace_back(); dfb(v,u,nuc); } } } int main() { ios::sync_with_stdio(0);cin.tie(0); int n; cin >> n; hl.assign(1,vi()); mac.assign(n,-1); g.assign(n,vi()); col.assign(n,-1); cop.assign(n,-1); sub.assign(n,-1); par.assign(n,-1); vector<pl> ord; for(int i=0;i<n;i++) { ll t; cin >> t; ord.push_back({t,i}); } sort(ord.begin(),ord.end()); po.assign(n,0); int rov = 0; for(int i=0;i<n;i++) { if(i > 0) { if(ord[i].first > ord[i].second) {rov = i;} } po[ord[i].second] = rov; } for(int i=1;i<n;i++) { int a,b; cin >> a >> b; a--;b--; eg.push_back({a,b}); g[a].push_back(b); g[b].push_back(a); } dfa(0,0); dfb(0,0,0); /* for(int i=0;i<n;i++) { cout << po[i] << " "; } cout << '\n'; for(int i=0;i<n;i++) { cout << col[i] << " "; } cout << '\n'; */ hac.assign(hl.size(),vpl()); for(int i=0;i<hl.size();i++) { for(int j=hl[i].size()-1;j>=0;j--) { int u = hl[i][j]; hac[i].push_back({po[u],1}); } } ST st(n); for(int idx=0;idx<eg.size();idx++) { vector<pl> ok; int u = eg[idx].first; int rep = po[eg[idx].second]; while(1) { int rs = 0; int co = col[u]; int rec = cop[u]+1; stack<pl> te; while(rs < rec) { pl wa = hac[co].back();hac[co].pop_back(); if(rs+wa.second > rec) { hac[co].push_back({wa.first,wa.second+rs-rec}); wa.second = rec-rs; } te.push(wa); rs += wa.second; } hac[co].push_back({rep,rec}); u = hl[col[u]][0]; while(!te.empty()) {ok.push_back(te.top());te.pop();} if(u == 0) {break;} u = par[u]; } ll res = 0; for(int i=0;i<ok.size();i++) { int num = ok[i].second; int pv = ok[i].first; res += st.get(0,pv)*num; st.up(pv,num); } for(int i=0;i<ok.size();i++) { int num = ok[i].second; int pv = ok[i].first; st.up(pv,-num); } cout << res << '\n'; } }

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

construction.cpp: In function 'int dfa(int, int)':
construction.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++) {
              ~^~~~~~~~~~~~
construction.cpp: In function 'void dfb(int, int, int)':
construction.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++) {
              ~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<hl.size();i++) {
              ~^~~~~~~~~~
construction.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int idx=0;idx<eg.size();idx++) {
                ~~~^~~~~~~~~~
construction.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ok.size();i++) {
               ~^~~~~~~~~~
construction.cpp:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ok.size();i++) {
               ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...