oj.uz

답안 #234687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234687 2020-05-25T07:49:58 Z AlexLuchianov Construction of Highway (JOI18_construction) C++14
7 / 100
 1022 ms 141436 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <map>
#include <stack>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int v[1 + nmax];
int ord[1 + nmax];

map<int,int> mp;

void normalize(int n){
  vector<int> temp;
  for(int i = 1;i <= n; i++)
    temp.push_back(v[i]);
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    mp[temp[i]] = 1 + i;
  for(int i = 1;i <= n; i++)
    v[i] = mp[v[i]];
}

namespace FenwickTree{
  vector<int> aib;
  int n;
  void initialize(int n_){
    n = n_;
    aib.resize(1 + n);
  }
  vector<int> touched;

  void clean(){
    for(int h = 0; h < touched.size(); h++)
      aib[touched[h]] = 0;
  }

  void update(int pos, int val){
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1)))) {
      aib[x] += val;
      touched.push_back(x);
    }
  }
  int query(int pos){
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }
}

namespace HLD{
  vector<int> g[1 + nmax];
  int far[1 + nmax], sz[1 + nmax];
  void dfs(int node){
    sz[node] = 1;
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      far[to] = node;
      dfs(to);
      sz[node] += sz[to];
    }
  }
  int ptr = 0;

  vector<int> path, path_position;
  vector<int> chain_father, chain_size;
  stack<pair<int,int>> st[1 + nmax];

  void _partition(int node, int curr){
    path[node] = curr;
    path_position[node] = ++chain_size[curr];
    if(path_position[node] == 1)
      chain_father[curr] = node;

    int best = 0;
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(sz[best] < sz[to])
        best = to;
    }
    if(0 < best)
      _partition(best, curr);

    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(to != best)
        _partition(to, ++ptr);
    }
  }

  void intialize(int n){
    path.resize(1 + n);
    path_position.resize(1 + n);
    chain_father.resize(1 + n);
    chain_size.resize(1 + n);

    ptr = 0;
    dfs(1);
    _partition(1, ++ptr);

    for(int i = 1;i <= ptr; i++)
      st[i].push({chain_size[i], 1});
  }

  vector<pair<int,int>> _affect(int chain, int pos, int val){
    vector<pair<int,int>> work;

    int last = 0;
    while(0 < st[chain].size() && st[chain].top().first <= pos){
      work.push_back({st[chain].top().first - last, st[chain].top().second});
      last = st[chain].top().first;
      st[chain].pop();
    }
    if(last < pos)
      work.push_back({pos - last, st[chain].top().second});
    st[chain].push({pos, val});
    return work;
  }

  ll query(int node, int val){
    vector<pair<int,int>> work;
    int steps = 0;

    while(0 < node){
      int curr = path[node];
      int pos = path_position[node];
      vector<pair<int,int>> work2 = _affect(curr, pos, val);
      node = far[chain_father[curr]];
      reverse(work2.begin(), work2.end());
      work.insert(work.end(), work2.begin(), work2.end());
      steps++;
      if(40 < steps){
        cout << "asdfasdf" << 3 / 0 << '\n';
        while(1);
        return 0;
      }
    }
    reverse(work.begin(), work.end());

    ll result = 0;
    FenwickTree::clean();

    for(int i = work.size() - 1; 0 <= i; i--){
      result += 1LL * FenwickTree::query(work[i].second - 1) * work[i].first;
      FenwickTree::update(work[i].second, work[i].first);
    }
    return result;
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  normalize(n);
  ord[1] = 1;
  for(int i = 2; i <= n; i++) {
    int farp;
    cin >> farp >> ord[i];
    HLD::g[farp].push_back(ord[i]);
  }

  HLD::intialize(n);
  FenwickTree::initialize(n);
  for(int i = n;1 <= i; i--)
    HLD::query(ord[i], v[ord[i]]);

  if(1000 < n)
    return 0;

  for(int i = 2; i <= n; i++){
    int node = ord[i];
    cout << HLD::query(HLD::far[node], v[node]) << '\n';
  }

  return 0;
}
/*

10
1 100 3 4 8 6 2 9 10 0
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/

Compilation message

construction.cpp: In function 'void normalize(int)':
construction.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
construction.cpp: In function 'void FenwickTree::clean()':
construction.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < touched.size(); h++)
                    ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'void HLD::dfs(int)':
construction.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'void HLD::_partition(int, int)':
construction.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
construction.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'll HLD::query(int, int)':
construction.cpp:143:33: warning: division by zero [-Wdiv-by-zero]
         cout << "asdfasdf" << 3 / 0 << '\n';
                               ~~^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 139768 KB Output is correct
2 Correct 99 ms 139620 KB Output is correct
3 Correct 108 ms 139768 KB Output is correct
4 Correct 119 ms 139768 KB Output is correct
5 Correct 140 ms 140152 KB Output is correct
6 Correct 139 ms 139896 KB Output is correct
7 Correct 130 ms 139896 KB Output is correct
8 Correct 124 ms 139768 KB Output is correct
9 Correct 137 ms 139768 KB Output is correct
10 Correct 135 ms 139768 KB Output is correct
11 Correct 136 ms 139896 KB Output is correct
12 Correct 130 ms 139896 KB Output is correct
13 Correct 125 ms 139896 KB Output is correct
14 Correct 129 ms 139896 KB Output is correct
15 Correct 158 ms 140152 KB Output is correct
16 Correct 157 ms 140152 KB Output is correct
17 Correct 159 ms 140152 KB Output is correct
18 Correct 159 ms 140284 KB Output is correct
19 Correct 124 ms 139952 KB Output is correct
20 Correct 122 ms 139896 KB Output is correct
21 Correct 125 ms 139896 KB Output is correct
22 Correct 150 ms 140152 KB Output is correct
23 Correct 147 ms 140024 KB Output is correct
24 Correct 140 ms 140024 KB Output is correct
25 Correct 138 ms 139900 KB Output is correct
26 Correct 119 ms 139896 KB Output is correct
27 Correct 117 ms 139896 KB Output is correct
28 Correct 121 ms 139896 KB Output is correct
29 Correct 124 ms 139896 KB Output is correct
30 Correct 130 ms 140152 KB Output is correct
31 Correct 152 ms 140152 KB Output is correct
32 Correct 133 ms 139900 KB Output is correct
33 Correct 129 ms 139896 KB Output is correct
34 Correct 129 ms 139896 KB Output is correct
35 Correct 128 ms 139896 KB Output is correct
36 Correct 136 ms 139964 KB Output is correct
37 Correct 137 ms 139900 KB Output is correct
38 Correct 136 ms 139896 KB Output is correct
39 Correct 127 ms 139952 KB Output is correct
40 Correct 128 ms 139896 KB Output is correct
41 Correct 130 ms 139884 KB Output is correct
42 Correct 137 ms 139896 KB Output is correct
43 Correct 138 ms 140024 KB Output is correct
44 Correct 139 ms 139896 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 139768 KB Output is correct
2 Correct 99 ms 139620 KB Output is correct
3 Correct 108 ms 139768 KB Output is correct
4 Correct 119 ms 139768 KB Output is correct
5 Correct 140 ms 140152 KB Output is correct
6 Correct 139 ms 139896 KB Output is correct
7 Correct 130 ms 139896 KB Output is correct
8 Correct 124 ms 139768 KB Output is correct
9 Correct 137 ms 139768 KB Output is correct
10 Correct 135 ms 139768 KB Output is correct
11 Correct 136 ms 139896 KB Output is correct
12 Correct 130 ms 139896 KB Output is correct
13 Correct 125 ms 139896 KB Output is correct
14 Correct 129 ms 139896 KB Output is correct
15 Correct 158 ms 140152 KB Output is correct
16 Correct 157 ms 140152 KB Output is correct
17 Correct 159 ms 140152 KB Output is correct
18 Correct 159 ms 140284 KB Output is correct
19 Correct 124 ms 139952 KB Output is correct
20 Correct 122 ms 139896 KB Output is correct
21 Correct 125 ms 139896 KB Output is correct
22 Correct 150 ms 140152 KB Output is correct
23 Correct 147 ms 140024 KB Output is correct
24 Correct 140 ms 140024 KB Output is correct
25 Correct 138 ms 139900 KB Output is correct
26 Correct 119 ms 139896 KB Output is correct
27 Correct 117 ms 139896 KB Output is correct
28 Correct 121 ms 139896 KB Output is correct
29 Correct 124 ms 139896 KB Output is correct
30 Correct 130 ms 140152 KB Output is correct
31 Correct 152 ms 140152 KB Output is correct
32 Correct 133 ms 139900 KB Output is correct
33 Correct 129 ms 139896 KB Output is correct
34 Correct 129 ms 139896 KB Output is correct
35 Correct 128 ms 139896 KB Output is correct
36 Correct 136 ms 139964 KB Output is correct
37 Correct 137 ms 139900 KB Output is correct
38 Correct 136 ms 139896 KB Output is correct
39 Correct 127 ms 139952 KB Output is correct
40 Correct 128 ms 139896 KB Output is correct
41 Correct 130 ms 139884 KB Output is correct
42 Correct 137 ms 139896 KB Output is correct
43 Correct 138 ms 140024 KB Output is correct
44 Correct 139 ms 139896 KB Output is correct
45 Correct 249 ms 140128 KB Output is correct
46 Incorrect 1022 ms 141436 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 139768 KB Output is correct
2 Correct 99 ms 139620 KB Output is correct
3 Correct 108 ms 139768 KB Output is correct
4 Correct 119 ms 139768 KB Output is correct
5 Correct 140 ms 140152 KB Output is correct
6 Correct 139 ms 139896 KB Output is correct
7 Correct 130 ms 139896 KB Output is correct
8 Correct 124 ms 139768 KB Output is correct
9 Correct 137 ms 139768 KB Output is correct
10 Correct 135 ms 139768 KB Output is correct
11 Correct 136 ms 139896 KB Output is correct
12 Correct 130 ms 139896 KB Output is correct
13 Correct 125 ms 139896 KB Output is correct
14 Correct 129 ms 139896 KB Output is correct
15 Correct 158 ms 140152 KB Output is correct
16 Correct 157 ms 140152 KB Output is correct
17 Correct 159 ms 140152 KB Output is correct
18 Correct 159 ms 140284 KB Output is correct
19 Correct 124 ms 139952 KB Output is correct
20 Correct 122 ms 139896 KB Output is correct
21 Correct 125 ms 139896 KB Output is correct
22 Correct 150 ms 140152 KB Output is correct
23 Correct 147 ms 140024 KB Output is correct
24 Correct 140 ms 140024 KB Output is correct
25 Correct 138 ms 139900 KB Output is correct
26 Correct 119 ms 139896 KB Output is correct
27 Correct 117 ms 139896 KB Output is correct
28 Correct 121 ms 139896 KB Output is correct
29 Correct 124 ms 139896 KB Output is correct
30 Correct 130 ms 140152 KB Output is correct
31 Correct 152 ms 140152 KB Output is correct
32 Correct 133 ms 139900 KB Output is correct
33 Correct 129 ms 139896 KB Output is correct
34 Correct 129 ms 139896 KB Output is correct
35 Correct 128 ms 139896 KB Output is correct
36 Correct 136 ms 139964 KB Output is correct
37 Correct 137 ms 139900 KB Output is correct
38 Correct 136 ms 139896 KB Output is correct
39 Correct 127 ms 139952 KB Output is correct
40 Correct 128 ms 139896 KB Output is correct
41 Correct 130 ms 139884 KB Output is correct
42 Correct 137 ms 139896 KB Output is correct
43 Correct 138 ms 140024 KB Output is correct
44 Correct 139 ms 139896 KB Output is correct
45 Correct 249 ms 140128 KB Output is correct
46 Incorrect 1022 ms 141436 KB Output isn't correct
47 Halted 0 ms 0 KB -