Submission #45985

#TimeUsernameProblemLanguageResultExecution timeMemory
45985octopusesConstruction of Highway (JOI18_construction)C++17
16 / 100
1083 ms11452 KiB
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second #define M -100000000000ll using namespace std; const int N = 200020; map < int, int > mp; int n, m, timer; int a[N], in[N], tn[N], out[N], P[N][20], dep[N]; pair < int, int > g[N]; vector < pair < int, int > > c; vector < int > G[N]; int T[4 * N], tot; ll t[4 * N]; void go(int v) { for(int k = 1; k < 20; ++ k) P[v][k] = P[P[v][k - 1]][k - 1]; dep[v] = dep[P[v][0]] + 1; in[v] = ++ timer; tn[timer] = v; for(auto x : G[v]) P[x][0] = v, go(x); out[v] = timer + 1; } int lca(int v, int u) { if(dep[u] < dep[v]) swap(u, v); for(int k = 19; k >= 0; -- k) if(dep[P[u][k]] >= dep[v]) u = P[u][k]; if(u == v) return v; for(int k = 19; k >= 0; -- k) if(P[u][k] != P[v][k]) u = P[u][k], v = P[v][k]; return P[u][0]; } void update(int v, int tl, int tr, int l, int x) { if(tl > l || tr <= l) return; if(tl == tr - 1) { T[v] = x; return; } update(v + v, tl, tl + tr >> 1, l, x); update(v + v + 1, tl + tr >> 1, tr, l, x); T[v] = max(T[v + v], T[v + v + 1]); } int get(int v, int tl, int tr, int l, int r) { if(tr <= l || r <= tl) return 0; if(l <= tl && tr <= r) return T[v]; int x, y; x = get(v + v, tl, tl + tr >> 1, l, r); y = get(v + v + 1, tl + tr >> 1, tr, l, r); return max(x, y); } void deep(int v) { if(v == 0) return; int x = get(1, 1, n + 1, in[v], out[v]); int r = out[v]; for(int k = 17; k >= 0; -- k) if(get(1, 1, n + 1, out[v], r + (1 << k)) <= x) r += 1 << k; if(r >= n + 1) r = 0; r = tn[r]; r = lca(r, v); int l = in[v]; for(int k = 17; k >= 0; -- k) if(get(1, 1, n + 1, l - (1 << k), in[v]) <= x) l -= 1 << k; l --; if(l <= 0) l = 0; l = tn[l]; l = lca(l, v); l = dep[l] < dep[r] ? r : l; c.push_back({a[g[x].sc], dep[v] - dep[l]}); deep(l); } void upd(int v, int tl, int tr, int l, ll x) { if(tl > l || tr <= l) return; if(tl == tr - 1) { if(x < 0) t[v] = 0; else t[v] += x; return; } upd(v + v, tl, tl + tr >> 1, l, x); upd(v + v + 1, tl + tr >> 1, tr, l, x); t[v] = t[v + v] + t[v + v + 1]; } ll gt(int v, int tl, int tr, int l) { if(tl >= l) return 0; if(tr <= l) return t[v]; return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l); } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]), mp[a[i]] = 1; m = 1; for(map < int, int >::iterator it = mp.begin(); it != mp.end(); it ++) it -> sc = m ++; for(int i = 1; i <= n; ++ i) a[i] = mp[a[i]]; for(int i = 2; i <= n; ++ i) { scanf("%d %d", &g[i].fr, &g[i].sc); G[g[i].fr].push_back(g[i].sc); } go(1); update(1, 1, n + 1, in[1], 1); g[1].sc = 1; for(int i = 2; i <= n; ++ i) { c.clear(); deep(g[i].fr); ll answer = 0; for(int j = 0; j < c.size(); ++ j) { answer += c[j].sc * gt(1, 1, m, c[j].fr); upd(1, 1, m, c[j].fr, c[j].sc); } for(int j = 0; j < c.size(); ++ j) upd(1, 1, m, c[j].fr, -10); printf("%lld\n", answer); update(1, 1, n + 1, in[g[i].sc], i); } }

Compilation message (stderr)

construction.cpp: In function 'void update(int, int, int, int, int)':
construction.cpp:56:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update(v + v, tl, tl + tr >> 1, l, x);
                     ~~~^~~~
construction.cpp:57:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update(v + v + 1, tl + tr >> 1, tr, l, x);
                     ~~~^~~~
construction.cpp: In function 'int get(int, int, int, int, int)':
construction.cpp:68:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = get(v + v, tl, tl + tr >> 1, l, r);
                      ~~~^~~~
construction.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   y = get(v + v + 1, tl + tr >> 1, tr, l, r);
                      ~~~^~~~
construction.cpp: In function 'void upd(int, int, int, int, long long int)':
construction.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   upd(v + v, tl, tl + tr >> 1, l, x);
                  ~~~^~~~
construction.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   upd(v + v + 1, tl + tr >> 1, tr, l, x);
                  ~~~^~~~
construction.cpp: In function 'long long int gt(int, int, int, int)':
construction.cpp:122:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l);
                        ~~~^~~~
construction.cpp:122:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l);
                                                         ~~~^~~~
construction.cpp: In function 'int main()':
construction.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < c.size(); ++ j)
                    ~~^~~~~~~~~~
construction.cpp:154:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < c.size(); ++ j)
                    ~~^~~~~~~~~~
construction.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:130:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]), mp[a[i]] = 1;
     ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
construction.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &g[i].fr, &g[i].sc);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...