제출 #47412

#제출 시각아이디문제언어결과실행 시간메모리
47412mirbek01Construction of Highway (JOI18_construction)C++14
7 / 100
28 ms6904 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, c[N], a[N], b[N], h[N], fen[N], u[N]; int p[18][N], tin[N], tout[N], timer; int t[N * 4]; vector <int> vec, g[N], vcc; void dfs(int v, int pr = 0){ tin[v] = ++ timer; p[0][v] = pr; for(int i = 1; i <= 17; i ++) p[i][v] = p[i - 1][p[i - 1][v]]; for(int to : g[v]){ if(to == pr) continue; h[to] = h[v] + 1; dfs(to, v); } tout[v] = timer; } inline bool upper(int a, int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } inline int lca(int a, int b){ if(upper(a, b)) return a; if(upper(b, a)) return b; for(int i = 17; i >= 0; i --) if(p[i][a] && !upper(p[i][a], b)) a = p[i][a]; return p[0][a]; } inline void update(int pos, int val, int v = 1, int tl = 1, int tr = n){ if(tl == tr) t[v] = val; else { int tm = (tl + tr) >> 1; if(pos <= tm) update(pos, val, v << 1, tl, tm); else update(pos, val, (v << 1) | 1, tm + 1, tr); t[v] = max(t[v << 1], t[(v << 1) | 1]); } } inline int get(int l, int r, int v = 1, int tl = 1, int tr = n){ if(l > tr || tl > r) return 0; if(l <= tl && tr <= r) return t[v]; int tm = (tl + tr) >> 1; return max(get(l, r, v << 1, tl, tm), get(l, r, (v << 1) | 1, tm + 1, tr)); } inline void Update(int r, int val){ for(; r > 0; r = (r & (r + 1)) - 1){ fen[r] += val; if(!u[r]){ u[r] = 1; vcc.emplace_back(r); } } } inline int Get(int pos){ int res = 0; for(; pos <= n; pos |= pos + 1) res += fen[pos]; return res; } int main(){ ios_base::sync_with_stdio(0); scanf("%d", &n); for(int i = 1; i <= n; i ++){ scanf("%d", &c[i]); vec.emplace_back(c[i]); } sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); for(int i = 1; i <= n; i ++) c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1; for(int i = 1; i < n; i ++){ scanf("%d %d", &a[i], &b[i]); g[a[i]].emplace_back(b[i]); g[b[i]].emplace_back(a[i]); } h[1] = 1; dfs(1); int siz = 0; for(int i = 1; i < n; i ++){ int v = 1, prelca = 0; long long ans = 0; vcc.clear(); while(1){ siz ++; int mx = b[get(tin[v], tout[v])]; int LCA = lca(mx, a[i]); int f = h[LCA] - h[prelca], s = c[mx]; ans += Get(s + 1) * 1ll * f; Update(s, f); prelca = LCA; if(v == a[i]) break; int vv = a[i]; for(int i = 17; i >= 0; i --){ if(p[i][vv] && !upper(p[i][vv], LCA)) vv = p[i][vv]; } v = vv; } if(siz >= n * 7) assert(0); for(int j = 0; j < vcc.size(); j ++) fen[vcc[j]] = 0, u[vcc[j]] = 0; printf("%lld\n", ans); update(tin[b[i]], i); } }

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

construction.cpp: In function 'int main()':
construction.cpp:123:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vcc.size(); j ++)
                            ~~^~~~~~~~~~~~
construction.cpp:78:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
construction.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[i]);
             ~~~~~^~~~~~~~~~~~~
construction.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a[i], &b[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...