Submission #540210

#	Time	Username	Problem	Language	Result	Execution time	Memory
540210		inluminas	Construction of Highway (JOI18_construction)	C++14	100 / 100	328 ms	21300 KiB

construction

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=1e5+10;
int c[lmt],chld[lmt],par[lmt],head[lmt],ind=1,len[lmt],cind[lmt],pos[lmt],ps;
ll tree[lmt],ans;
vector<int>adj[lmt];
vector<pair<int,int>>path[lmt],a;



void dfs(int u,int p){
  chld[u]=1,par[u]=p;
  for(int v:adj[u]){
    if(v==p) continue;
    dfs(v,u);
    chld[u]+=chld[v];
  }
}

void hld(int u,int p){
  if(!head[ind]) head[ind]=u;

  len[ind]++;
  cind[u]=ind;
  pos[u]=++ps;

  int to=0;
  for(int v:adj[u]){
    if(v==p) continue;
    if(!to || chld[to]<chld[v]) to=v;
  }

  if(to) hld(to,u);

  for(int v:adj[u]){
    if(v==p || v==to) continue;
    ind++;
    hld(v,u);
  }
}

void f(int hi,int lo,int nw){
  int Len=pos[lo]-pos[hi]+1,till=0;
  int id=cind[hi];
  vector<pair<int,int>>b;
  while(till<Len){
    if(till+ path[id].back().first>Len){
      pair<int,int>x=path[id].back();
      path[id].pop_back();
      int dif=Len-till;
      b.emplace_back(dif,x.second);
      till=Len;
      path[id].emplace_back(x.first-dif,x.second);
      break;
    }else{
      pair<int,int>x=path[id].back();
      path[id].pop_back();
      b.push_back(x);
      till+=x.first;
    }
  }
  path[id].push_back({Len,nw});

  reverse(b.begin(),b.end());

  a.insert(a.end(),b.begin(),b.end());
}

ll query(int idx){
  ll sum=0;
  while(idx){
    sum+=tree[idx];
    idx-=(idx&-idx);
  }
  return sum;
}

void update(int idx,ll val,int sz){
  while(idx>0 && idx<=sz){
    tree[idx]+=val,idx+=(idx&-idx);
  }
}

int main(){
  fastio;

  int n;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>c[i];

  vector<pair<int,int>>e;

  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    e.push_back({u,v});
    adj[u].push_back(v);
  }

  dfs(1,0);
  hld(1,0);

  for(int i=1; head[i];i++){
    path[i].push_back({len[i],0});
  }


  for(auto [U,V]:e){
    int u=V,v=c[V];
    while(u){
      int id=cind[u];
      f(head[id],u,v);
      u=par[head[id]];
    }
    a[0].first--;

    vector<int>q;
    for(auto [x,y]:a){
      if(x==0) continue;
      q.push_back(y);
    }

    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());

    map<int,int>ID;
    int o=0;
    for(int x:q){
      ID[x]=++o;
    }

    for(auto &x:a){
      if(x.first==0) continue;
      x.second=ID[x.second];
    }

    for(auto [x,y]:a){
      if(x==0) continue;

      ans+=x*query(y-1);
      update(y,x,o);
    }

    for(int i=1;i<=o;i++) tree[i]=0;

    cout<<ans<<endl;
    ans=0;

    a.clear();
  }

  return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:114:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |   for(auto [U,V]:e){
      |            ^
construction.cpp:124:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for(auto [x,y]:a){
      |              ^
construction.cpp:143:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |     for(auto [x,y]:a){
      |              ^

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