Submission #47399

#	Time	Username	Problem	Language	Result	Execution time	Memory
47399		mirbek01	Construction of Highway (JOI18_construction)	C++17	16 / 100	1085 ms	29584 KiB

construction

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, c[N], a[N], b[N], h[N], fen[N];
int p[18][N], tin[N], tout[N], timer;
pair <int, int> t[N * 4];
vector <int> vec, g[N];


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 vv, int v = 1, int tl = 1, int tr = n){
      if(tl == tr)
            t[v] = {val, vv};
      else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  update(pos, val, vv, v << 1, tl, tm);
            else
                  update(pos, val, vv, (v << 1) | 1, tm + 1, tr);
            t[v] = max(t[v << 1], t[(v << 1) | 1]);
      }
}

inline pair <int, int> get(int l, int r, int v = 1, int tl = 1, int tr = n){
      if(l > tr || tl > r) return {0, 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;
}

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, lg = ceil(log2(n));
      for(int i = 1; i < n; i ++){
            int v = 1, prelca = 0;
            vector < pair <int, int> > vc;
            while(1){
                  pair <int, int> mx = get(tin[v], tout[v]);
                  int LCA  = lca(mx.second, a[i]);
                  vc.push_back({h[LCA] - h[prelca], c[mx.second]});
                  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;
            }

            long long ans = 0;
            siz += vc.size();
            if(siz > n * lg){
                  assert(0);
            }
            for(int j = 0; j < vc.size(); j ++){
                  int f = vc[j].first, s = vc[j].second;
                  ans += Get(s + 1) * f;
                  Update(s, f);
            }
            printf("%I64d\n", ans);
            update(tin[b[i]], i, b[i]);
            for(int j = 0; j < vc.size(); j ++){
                  int f = vc[j].first, s = vc[j].second;
                  Update(s, -f);
            }
      }
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:118:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vc.size(); j ++){
                            ~~^~~~~~~~~~~
construction.cpp:123:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
             printf("%I64d\n", ans);
                                  ^
construction.cpp:125:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vc.size(); j ++){
                            ~~^~~~~~~~~~~
construction.cpp:74:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
construction.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[i]);
             ~~~~~^~~~~~~~~~~~~
construction.cpp:88: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]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84