oj.uz

Submission #45981

# Submission time Handle Problem Language Result Execution time Memory
45981 2018-04-16T19:52:30 Z octopuses Construction of Highway (JOI18_construction) C++17
7 / 100
 9 ms 3708 KB 
#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);
    if(tot > S * 40)
      return 0;
    printf("%lld\n", answer);
    update(1, 1, n + 1, in[g[i].sc], i);
  }
}

Compilation message

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);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 3024 KB Output is correct
6 Correct 6 ms 3024 KB Output is correct
7 Correct 5 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 5 ms 3028 KB Output is correct
10 Correct 4 ms 3028 KB Output is correct
11 Correct 5 ms 3028 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 7 ms 3028 KB Output is correct
14 Correct 4 ms 3052 KB Output is correct
15 Correct 7 ms 3068 KB Output is correct
16 Correct 7 ms 3068 KB Output is correct
17 Correct 7 ms 3072 KB Output is correct
18 Correct 7 ms 3148 KB Output is correct
19 Correct 5 ms 3148 KB Output is correct
20 Correct 5 ms 3148 KB Output is correct
21 Correct 5 ms 3148 KB Output is correct
22 Correct 7 ms 3148 KB Output is correct
23 Correct 6 ms 3148 KB Output is correct
24 Correct 6 ms 3148 KB Output is correct
25 Correct 7 ms 3148 KB Output is correct
26 Correct 4 ms 3148 KB Output is correct
27 Correct 5 ms 3148 KB Output is correct
28 Correct 4 ms 3148 KB Output is correct
29 Correct 6 ms 3148 KB Output is correct
30 Correct 7 ms 3148 KB Output is correct
31 Correct 7 ms 3148 KB Output is correct
32 Correct 5 ms 3148 KB Output is correct
33 Correct 5 ms 3148 KB Output is correct
34 Correct 6 ms 3148 KB Output is correct
35 Correct 6 ms 3148 KB Output is correct
36 Correct 5 ms 3148 KB Output is correct
37 Correct 6 ms 3148 KB Output is correct
38 Correct 4 ms 3148 KB Output is correct
39 Correct 5 ms 3176 KB Output is correct
40 Correct 5 ms 3176 KB Output is correct
41 Correct 6 ms 3176 KB Output is correct
42 Correct 5 ms 3176 KB Output is correct
43 Correct 5 ms 3176 KB Output is correct
44 Correct 5 ms 3176 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 3024 KB Output is correct
6 Correct 6 ms 3024 KB Output is correct
7 Correct 5 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 5 ms 3028 KB Output is correct
10 Correct 4 ms 3028 KB Output is correct
11 Correct 5 ms 3028 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 7 ms 3028 KB Output is correct
14 Correct 4 ms 3052 KB Output is correct
15 Correct 7 ms 3068 KB Output is correct
16 Correct 7 ms 3068 KB Output is correct
17 Correct 7 ms 3072 KB Output is correct
18 Correct 7 ms 3148 KB Output is correct
19 Correct 5 ms 3148 KB Output is correct
20 Correct 5 ms 3148 KB Output is correct
21 Correct 5 ms 3148 KB Output is correct
22 Correct 7 ms 3148 KB Output is correct
23 Correct 6 ms 3148 KB Output is correct
24 Correct 6 ms 3148 KB Output is correct
25 Correct 7 ms 3148 KB Output is correct
26 Correct 4 ms 3148 KB Output is correct
27 Correct 5 ms 3148 KB Output is correct
28 Correct 4 ms 3148 KB Output is correct
29 Correct 6 ms 3148 KB Output is correct
30 Correct 7 ms 3148 KB Output is correct
31 Correct 7 ms 3148 KB Output is correct
32 Correct 5 ms 3148 KB Output is correct
33 Correct 5 ms 3148 KB Output is correct
34 Correct 6 ms 3148 KB Output is correct
35 Correct 6 ms 3148 KB Output is correct
36 Correct 5 ms 3148 KB Output is correct
37 Correct 6 ms 3148 KB Output is correct
38 Correct 4 ms 3148 KB Output is correct
39 Correct 5 ms 3176 KB Output is correct
40 Correct 5 ms 3176 KB Output is correct
41 Correct 6 ms 3176 KB Output is correct
42 Correct 5 ms 3176 KB Output is correct
43 Correct 5 ms 3176 KB Output is correct
44 Correct 5 ms 3176 KB Output is correct
45 Correct 9 ms 3196 KB Output is correct
46 Incorrect 8 ms 3708 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 3024 KB Output is correct
6 Correct 6 ms 3024 KB Output is correct
7 Correct 5 ms 3028 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 5 ms 3028 KB Output is correct
10 Correct 4 ms 3028 KB Output is correct
11 Correct 5 ms 3028 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 7 ms 3028 KB Output is correct
14 Correct 4 ms 3052 KB Output is correct
15 Correct 7 ms 3068 KB Output is correct
16 Correct 7 ms 3068 KB Output is correct
17 Correct 7 ms 3072 KB Output is correct
18 Correct 7 ms 3148 KB Output is correct
19 Correct 5 ms 3148 KB Output is correct
20 Correct 5 ms 3148 KB Output is correct
21 Correct 5 ms 3148 KB Output is correct
22 Correct 7 ms 3148 KB Output is correct
23 Correct 6 ms 3148 KB Output is correct
24 Correct 6 ms 3148 KB Output is correct
25 Correct 7 ms 3148 KB Output is correct
26 Correct 4 ms 3148 KB Output is correct
27 Correct 5 ms 3148 KB Output is correct
28 Correct 4 ms 3148 KB Output is correct
29 Correct 6 ms 3148 KB Output is correct
30 Correct 7 ms 3148 KB Output is correct
31 Correct 7 ms 3148 KB Output is correct
32 Correct 5 ms 3148 KB Output is correct
33 Correct 5 ms 3148 KB Output is correct
34 Correct 6 ms 3148 KB Output is correct
35 Correct 6 ms 3148 KB Output is correct
36 Correct 5 ms 3148 KB Output is correct
37 Correct 6 ms 3148 KB Output is correct
38 Correct 4 ms 3148 KB Output is correct
39 Correct 5 ms 3176 KB Output is correct
40 Correct 5 ms 3176 KB Output is correct
41 Correct 6 ms 3176 KB Output is correct
42 Correct 5 ms 3176 KB Output is correct
43 Correct 5 ms 3176 KB Output is correct
44 Correct 5 ms 3176 KB Output is correct
45 Correct 9 ms 3196 KB Output is correct
46 Incorrect 8 ms 3708 KB Output isn't correct
47 Halted 0 ms 0 KB -