Submission #933008

#	Time	Username	Problem	Language	Result	Execution time	Memory
933008		velislavgarkov	Construction of Highway (JOI18_construction)	C++14	100 / 100	1301 ms	27992 KiB

construction

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int MAXN=1e5+10;
#define endl '\n'
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int ss[MAXN], par[MAXN];
int heavy[MAXN], start[MAXN], op[MAXN], seg_pos[MAXN];
int heavy_cnt, cnt;
int tree[4*MAXN], lazy[4*MAXN];
int fen[MAXN];
unordered_map <int,int> um;
vector <int> v[MAXN];
vector <pair <int,long long> > arr;
int n;
void dfs(int x, int p) {
    ss[x]=0;
    for (auto i:v[x]) {
        if (i==p) continue;
        dfs(i,x);
        par[i]=x;
        ss[x]=max(ss[x],ss[i]+1);
    }
}
void decompose(int x, int curh) {
    seg_pos[x]=cnt;
    heavy[x]=curh;
    op[cnt]=x;
    cnt++;
    int maxind=-1;
    for (auto i:v[x]) {
        if (i==par[x]) continue;
        if (maxind==-1 || ss[maxind]<ss[i]) maxind=i;
    }
    if (maxind==-1) return;
    decompose(maxind,curh);
    for (auto i:v[x]) {
        if (i==par[x] || i==maxind) continue;
        heavy_cnt++;
        start[heavy_cnt]=i;
        decompose(i,heavy_cnt);
    }
}
int combine(int l, int r) {
    if (l==-2) return r;
    if (r==-2) return l;
    if (l==r) return l;
    return -1;
}
void push_lazy(int node, int l, int r) {
    if (!lazy[node]) return;
    if (l!=r) {
        lazy[node*2]=lazy[node*2+1]=lazy[node];
        tree[node*2]=tree[node*2+1]=lazy[node];
    }
    lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr, int ch) {
    if (ql>r || qr<l) return;
    push_lazy(node,l,r);
    if (l>=ql && r<=qr) {
        tree[node]=lazy[node]=ch;
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr,ch);
    update(node*2+1,mid+1,r,ql,qr,ch);
    tree[node]=combine(tree[node*2],tree[node*2+1]);
}
int query(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return -2;
    push_lazy(node,l,r);
    if (l>=ql && r<=qr) return tree[node];
    int mid=(l+r)/2;
    return combine(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
void add_edge(int x, int val) {
    while (x!=-1) {
        int nxt=start[heavy[x]];
        update(1,1,n,seg_pos[nxt],seg_pos[x],val);
        x=par[nxt];
    }
}
void update_fen(int ind, int ch) {
    while (ind<=n) {
        fen[ind]+=ch;
        ind+=(ind & (-ind));
    }
}
int query_fen(int ind) {
    int res=0;
    while (ind>0) {
        res+=fen[ind];
        ind-=(ind & (-ind));
    }
    return res;
}
int find_next(int l, int r, int val) {
    int cur=r;
    int mid;
    while (l<=r) {
        mid=(l+r)/2;
        if (query(1,1,n,mid,cur)==val) r=mid-1;
        else l=mid+1;
    }
    return op[r];
}
long long find_ans(int x) {
    if (!arr.empty()) arr.clear();
    int sa=-1;
    while (x!=-1) {
        int curv=query(1,1,n,seg_pos[x],seg_pos[x]);
        arr.push_back({curv,0});
        sa++;
        int nxt;
        while (x!=-1) {
            nxt=start[heavy[x]];
            int s=query(1,1,n,seg_pos[nxt],seg_pos[x]);
            if (s!=curv) break;
            arr[sa].second+=seg_pos[x]-seg_pos[nxt]+1;
            x=par[nxt];
        }
        if (x!=-1) {
            int newx=find_next(seg_pos[nxt],seg_pos[x],curv);
            arr[sa].second+=seg_pos[x]-seg_pos[newx];
            x=newx;
        }
    }
    long long ans=0;
    for (int i=arr.size()-1;i>=0;i--) {
        long long curs=query_fen(n)-query_fen(arr[i].first);
        curs*=arr[i].second;
        ans+=curs;
        update_fen(arr[i].first,arr[i].second);
    }
    for (int i=0;i<arr.size();i++) update_fen(arr[i].first,-arr[i].second);
    return ans;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> c[i];
        d[i]=c[i];
    }
    sort(d+1,d+n+1);
    for (int i=1;i<=n;i++) {
        if (um[d[i]]==0) um[d[i]]=i;
    }
    for (int i=1;i<=n;i++) c[i]=um[c[i]];
    for (int i=0;i<n-1;i++) {
        cin >> a[i] >> b[i];
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    dfs(1,-1);
    start[1]=1;
    heavy_cnt=cnt=1;
    par[1]=-1;
    decompose(1,1);
    update(1,1,n,1,1,1);
    for (int i=0;i<n-1;i++) {
        cout << find_ans(a[i]) << endl;
        add_edge(b[i],c[b[i]]);
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'long long int find_ans(int)':
construction.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i=0;i<arr.size();i++) update_fen(arr[i].first,-arr[i].second);
      |                  ~^~~~~~~~~~~

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