제출 #529074

#제출 시각아이디문제언어결과실행 시간메모리
5290748e7Construction of Highway (JOI18_construction)C++17
100 / 100
255 ms21336 KiB
//Challenge: Accepted #include <bits/stdc++.h> using namespace std; #ifdef zisk void debug(){cout << endl;} template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);} template<class T> void pary(T l, T r) { while (l != r) cout << *l << " ", l++; cout << endl; } #else #define debug(...) 0 #define pary(...) 0 #endif #define ll long long #define maxn 100005 #define pii pair<int, int> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); struct BIT{ ll bit[maxn]; vector<pii> ch; void modify(int ind, int val) { ch.push_back({ind, val}); for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val; } ll query(int ind) { ll ret = 0; for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind]; return ret; } void rev() { for (auto [ind, val]:ch) { for (;ind < maxn;ind += ind & (-ind)) bit[ind] -= val; } ch.clear(); } } bit; vector<int> adj[maxn]; int c[maxn], par[maxn], siz[maxn], dep[maxn], ti[maxn], up[maxn], ord[maxn]; int nxt[maxn]; void getsiz(int n, int pa, int d) { dep[n] = d; siz[n] = 1; for (int v:adj[n]) { getsiz(v, n, d+1); siz[n] += siz[v]; } } void mark(int n, int pa, int vi) { up[n] = vi; int best = 0, bind = 0; for (int v:adj[n]) { if (siz[v] > best) { best = siz[v], bind = v; } } nxt[n] = bind; for (int v:adj[n]) { if (v != bind) { mark(v, n, v); } else { mark(v, n, vi); } } } ll ans[maxn]; vector<pii> se[maxn]; int main() { io int n; cin >> n; vector<int> val; for (int i = 1;i <= n;i++) cin >> c[i], val.push_back(c[i]); sort(val.begin(), val.end()); val.resize(int(unique(val.begin(), val.end()) - val.begin())); for (int i = 1;i <= n;i++) c[i] = (lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1); for (int i = 1;i <= n - 1;i++) { int u, v; cin >> u >> v; par[v] = u; ti[v] = i; ord[i] = v; adj[u].push_back(v); } getsiz(1, 0, 0); mark(1, 0, 1); se[1].push_back({0, 1}); pary(up + 1, up + n + 1); for (int id = 1;id <= n - 1;id++) { int i = par[ord[id]], nc = c[ord[id]]; vector<pii> col; col.push_back({dep[ord[id]], maxn - 1}); debug(i); while (i) { //get all segments into col and update int p = up[i], di = dep[i] + 1, last = 0; vector<pii> &cur = se[p]; vector<pii> tmp; int siz = cur.size(); while (siz && cur.back().ff < di) { last = cur.back().ss; tmp.push_back(cur.back()); cur.pop_back(); siz--; } if (ti[nxt[i]] < id && !(siz && cur.back().ff == di)) cur.push_back({di, last}); cur.push_back({dep[p], nc}); reverse(tmp.begin(), tmp.end()); col.insert(col.end(), tmp.begin(), tmp.end()); for (auto x:cur) debug(x.ff, x.ss); i = par[p]; } i = ord[id]; //debug(col[0].ff, col[0].ss); for (int j = 1;j < col.size();j++) { //debug(col[j].ff, col[j].ss); ans[i] += bit.query(col[j].ss - 1) * (col[j-1].ff - col[j].ff); bit.modify(col[j].ss, col[j-1].ff - col[j].ff); } if (i == up[i]) { se[i].push_back({dep[i], c[i]}); } bit.rev(); } for (int i = 1;i <= n - 1;i++) cout << ans[ord[i]] << "\n"; } /* 7 1 2 3 4 5 6 1 1 2 2 3 3 4 3 5 2 6 4 7 9 1 4 5 2 7 3 6 3 1 1 2 1 3 3 4 4 5 4 6 1 7 2 8 5 9 10 1 5 8 6 7 2 9 3 4 10 1 5 1 8 5 9 8 3 5 4 8 6 9 7 3 10 4 2 */

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

construction.cpp: In function 'int main()':
construction.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
construction.cpp:96:2: note: in expansion of macro 'pary'
   96 |  pary(up + 1, up + n + 1);
      |  ^~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
construction.cpp:101:3: note: in expansion of macro 'debug'
  101 |   debug(i);
      |   ^~~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
construction.cpp:120:21: note: in expansion of macro 'debug'
  120 |    for (auto x:cur) debug(x.ff, x.ss);
      |                     ^~~~~
construction.cpp:120:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  120 |    for (auto x:cur) debug(x.ff, x.ss);
      |              ^
construction.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int j = 1;j < col.size();j++) {
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...