제출 #1305267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305267		vako_p	Construction of Highway (JOI18_construction)	C++20	16 / 100	2095 ms	18748 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,a[mxN],x[mxN],par[mxN],y[mxN];
vector<ll> v[mxN];

void dfs(ll at){
  for(auto it : v[at]){
    if(it == par[at]) continue;
    par[it] = at;
    dfs(it);
  }
}

struct fenwick{
  vector<ll> v;
  ll sz = 1;

  void init(){
    sz = n + 5;
    v.assign(sz, 0LL);
  }

  void set(ll val, ll i){
    while(i < sz){
      v[i] += val;
      i += i & -i;
    }
  }

  ll find(ll i){
    ll res = 0;
    while(i > 0){
      res += v[i]; 
      i -= i & -i;
    }
    return res;
  }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n;
  map<ll,ll> mp;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    mp[a[i]] = 1;
  } 
  ll cc = 0;
  for(auto &it : mp) it.sd = ++cc;
  for(int i = 1; i <= n; i++) a[i] = mp[a[i]];
  for(int i = 0; i < n - 1; i++){
    cin >> x[i] >> y[i];
    v[x[i]].pb(y[i]);
    v[y[i]].pb(x[i]);
  }
  dfs(1);
  for(int i = 0; i < n - 1; i++){
    ll ans = 0,at = x[i];
    fenwick s;
    s.init();
    while(at){
      // cout << at << ' ' << s.find(a[at] - 1) << endl;
      ans += s.find(a[at] - 1);
      s.set(1, a[at]);
      a[at] = a[y[i]];
      at = par[at];
    }
    cout << ans << '\n';
  }
}

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