Submission #45983

#TimeUsernameProblemLanguageResultExecution timeMemory
45983octopusesConstruction of Highway (JOI18_construction)C++17
16 / 100
1074 ms23228 KiB
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second #define M -100000000000ll using namespace std; const int N = 100020; 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); } int right(int v, int tl, int tr, int ind, int x) { tot ++; if(tr <= ind) return 0; if(tl < ind) { int y = right(v + v, tl, tl + tr >> 1, ind, x); if(y) return y; return right(v + v + 1, tl + tr >> 1, tr, ind, x); } if(T[v] <= x) return 0; if(tl == tr - 1) return tn[tl]; if(T[v + v] <= x) return right(v + v + 1, tl + tr >> 1, tr, ind, x); return right(v + v, tl, tl + tr >> 1, ind, x); } int left(int v, int tl, int tr, int ind, int x) { tot ++; if(tl >= ind) return 0; if(ind < tr) { int y = left(v + v + 1, tl + tr >> 1, tr, ind, x); if(y) return y; return left(v + v, tl, tl + tr >> 1, ind, x); } if(T[v] <= x) return 0; if(tl == tr - 1) return tn[tl]; if(T[v + v + 1] <= x) return left(v + v, tl, tl + tr >> 1, ind, x); return left(v + v + 1, tl + tr >> 1, tr, ind, x); } void deep(int v) { if(v == 0) return; int x = get(1, 1, n + 1, in[v], out[v]); int r = right(1, 1, n + 1, out[v], x); r = lca(r, v); int l = left(1, 1, n + 1, in[v], x); 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; int S = 0; for(int i = 2; i <= n; ++ i) { c.clear(); deep(g[i].fr); ll answer = 0; S += c.size(); 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); if(tot > n * 500) return 0; 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 'int right(int, int, int, int, int)':
construction.cpp:80:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int y = right(v + v, tl, tl + tr >> 1, ind, x);
                              ~~~^~~~
construction.cpp:83:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     return right(v + v + 1, tl + tr >> 1, tr, ind, x);
                             ~~~^~~~
construction.cpp:90:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     return right(v + v + 1, tl + tr >> 1, tr, ind, x);
                             ~~~^~~~
construction.cpp:91:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return right(v + v, tl, tl + tr >> 1, ind, x);
                           ~~~^~~~
construction.cpp: In function 'int left(int, int, int, int, int)':
construction.cpp:101:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int y = left(v + v + 1, tl + tr >> 1, tr, ind, x);
                             ~~~^~~~
construction.cpp:104:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     return left(v + v, tl, tl + tr >> 1, ind, x);
                            ~~~^~~~
construction.cpp:111:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     return left(v + v, tl, tl + tr >> 1, ind, x);
                            ~~~^~~~
construction.cpp:112:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return left(v + v + 1, tl + tr >> 1, tr, ind, x);
                          ~~~^~~~
construction.cpp: In function 'void upd(int, int, int, int, long long int)':
construction.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   upd(v + v, tl, tl + tr >> 1, l, x);
                  ~~~^~~~
construction.cpp:140: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:150: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:150: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:179:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < c.size(); ++ j)
                    ~~^~~~~~~~~~
construction.cpp:184:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < c.size(); ++ j)
                    ~~^~~~~~~~~~
construction.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:158: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:166: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...