Submission #47389

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

construction

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, c[N], p[N], fen[N];
vector <int> vec;

void update(int pos, int val){
      for(; pos <= n; pos |= pos + 1)
            fen[pos] += val;
}

int get(int pos){
      int res = 0;
      for(; pos > 0; pos = (pos & (pos + 1)) - 1)
            res += fen[pos];
      return res;
}

int main(){
      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;
      }
      int cc = 0;
      for(int i = 1; i < n; i ++){
            int a, b;
            scanf("%d %d", &a, &b);
            int v = a, ans = 0;
            set <int> st;
            while(v){
                  update(c[v], 1);
                  ans += get(c[v] - 1);
                  st.insert(c[v]);
                  v = p[v];
            }

            cc += st.size();

            v = a;
            while(v){
                  update(c[v], -1);
                  c[v] = c[b];
                  v = p[v];
            }
            printf("%d\n", ans);
            p[b] = a;
      }

      int lg = ceil(log2(n));
      if(cc > n * max((lg - 2), 1)) assert(0);
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:23:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
construction.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[i]);
             ~~~~~^~~~~~~~~~~~~
construction.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

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