Submission #47431

#	Time	Username	Problem	Language	Result	Execution time	Memory
47431		Just_Solve_The_Problem	Construction of Highway (JOI18_construction)	C++11	100 / 100	599 ms	68028 KiB

construction

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define random rand() ^ (rand() << 5)

const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;

struct fenwick {
  int tree[N];
  fenwick() {
    memset(tree, 0, sizeof tree);
  }
  void upd(int pos, int val) {
    for (; pos < N; pos += pos & -pos) {
      tree[pos] += val;
    }
  }
  int get(int r) {
    int res = 0;
    for (; r > 0; r -= r & -r) {
      res += tree[r];
    }
    return res;
  }
}tr;

struct data {
  int depth, val, cnt;
};

int n;
int c[N], b[N];
pii ar[N];
int pr[N], sz[N], h[N];
int chain[N], chainnum[N], chainsz[N], head[N];
int newchain = 2;
vector < int > gr[N];

void dfs(int v = 1) {
  sz[v] = 1;
  for (int to : gr[v]) {
    pr[to] = v;
    h[to] = h[v] + 1;
    dfs(to);
    sz[v] += sz[to];
  }
}

void buildhld(int v = 1, int curchain = 1) {
  chain[v] = curchain;
  if (!chainsz[curchain]) {
    head[curchain] = v;
  }
  chainnum[v] = ++chainsz[curchain];
  int siz = 0, big = -1;
  for (int to : gr[v]) {
    if (sz[to] > siz) {
      siz = sz[to];
      big = to;
    }
  }
  if (big != -1) {
    buildhld(big, curchain);
  }
  for (int to : gr[v]) {
    if (to == big) continue;
    buildhld(to, newchain++);
  }
}

vector < data > q[N];

ll calc(int v) {
  vector < data > temp;
  vector < pii > reset;
  int id, depth;
  ll ans = 0;
  while (v) {
    id = chain[v];
    depth = h[v];
//    printf("*** %d\n", v);
    while (!q[id].empty() && q[id].back().depth < depth) {
      temp.pb(q[id].back());
      q[id].pop_back();
    }
    if (!q[id].empty()) {
      data t = q[id].back();
      q[id].pop_back();
      int newcnt = t.depth - depth;
      t.cnt -= newcnt;
      temp.pb(t);
      t.cnt = newcnt;
      if (t.cnt)
        q[id].pb(t);
    }
    while (!temp.empty()) {
      data t = temp.back();
      temp.pop_back();
//      cout << v << ' ' << t.cnt << ' ' << t.val << endl;
      ans += t.cnt * tr.get(t.val - 1);
      tr.upd(t.val, t.cnt);
      reset.pb(mk(t.val, -t.cnt));
    }
    v = pr[head[id]];
  }
  for (auto to : reset) {
    tr.upd(to.fr, to.sc);
  }
  return ans;
}

void upd(int v) {
  data x;
  x.val = c[v];
  while (v) {
    int id = chain[v];
    x.cnt = chainnum[v];
    x.depth = h[v];
    q[id].pb(x);
    v = pr[head[id]];
  }
}

main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    b[i] = c[i];
  }
  sort(b + 1, b + n + 1);
  int m = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; i++) {
    c[i] = lower_bound(b + 1, b + m + 1, c[i]) - b;
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    gr[u].pb(v);
    ar[i] = mk(u, v);
  }
  dfs();
  buildhld();
  for (int i = 1; i < n; i++) {
    printf("%I64d\n", calc(ar[i].fr));
    upd(ar[i].sc);
  }
}

Compilation message (stderr)

construction.cpp:138:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
construction.cpp: In function 'int main()':
construction.cpp:158:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%I64d\n", calc(ar[i].fr));
                       ~~~~~~~~~~~~~~^
construction.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c[i]);
     ~~~~~^~~~~~~~~~~~~
construction.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~

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