Submission #47378

#	Time	Username	Problem	Language	Result	Execution time	Memory
47378		Just_Solve_The_Problem	Construction of Highway (JOI18_construction)	C++11	16 / 100	1077 ms	62024 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;
  }
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
}tr;

int n;
int c[N], b[N];
pii ar[N];
int pr[N];
vector < int > gr[N];
vector < int > vv[N];

void dfs(int v) {
  for (int to : gr[v]) {
    vv[to] = vv[v];
    vv[to].pb(v);
    dfs(to);
  }
}

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(1);
  for (int i = 1; i < n; i++) {
    int ans = 0;
    tr = fenwick();
    for (int j = sz(vv[ar[i].sc]) - 1; j >= 0; j--) {
      int val = vv[ar[i].sc][j];
      ans += tr.get(c[val] - 1);
      tr.upd(c[val], 1);
      c[val] = c[ar[i].sc];
    }

    printf("%d\n", ans);
  }
}

Compilation message (stderr)

construction.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
construction.cpp: In function 'int main()':
construction.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c[i]);
     ~~~~~^~~~~~~~~~~~~
construction.cpp:72: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: 0 / 84