Submission #204669

#	Time	Username	Problem	Language	Result	Execution time	Memory
204669		egekabas	Construction of Highway (JOI18_construction)	C++14	0 / 100	60 ms	70140 KiB

construction

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n;
vector<int> querry;
int val[100009];
vector<int> g[100009];
int prt[100009];
int subsz[100009];
int depth[100009];
int dfs1(int v){
    subsz[v] = 1;
    for(auto u : g[v]){
        prt[u] = v;
        depth[u] = depth[v]+1;
        dfs1(u);
        subsz[v] += subsz[u];
    }
}
int eul[100009];
int chain[100009];
ll cureul = 0;
int dfs2(int v){
    //cout << v << " -- " << cureul << '\n';
    eul[v] = cureul++;
    if(eul[prt[v]] == eul[v]-1)
        chain[v] = chain[prt[v]];
    else
        chain[v] = v;
    int biggest = 0, id = 0;
    for(auto u : g[v])
        if(subsz[u] > biggest){
            biggest = subsz[u];
            id = u;
        }
    if(id != 0)
        dfs2(id);
    for(auto u : g[v])
        if(u != id)
            dfs2(u);
}
deque<pll> vec[100009];

ll bit[100009];
void updbit(ll idx, ll val){
    ++idx;
    while(idx <= n){
        bit[idx] += val;
        idx += idx&(-idx);
    }
}
ll getbit(ll idx){
    ++idx;
    ll ret = 0;
    while(idx > 0){
        ret += bit[idx];
        idx -= idx&(-idx);
    }
    return ret;
}

ll gettree(ll idx){
    ll ret = 0;
    vector<ll> erase;
    while(idx != 0){
        deque<pll> &v = vec[chain[idx]];
        auto it = upper_bound(v.begin(), v.end(), mp(idx,ll(1e9)));
        if(it == v.end())--it;
        while(1){
            int bef = depth[chain[idx]];
            if(it != v.begin())
                bef = depth[(*(it-1)).ff]+1;
            
            int cnt = min(depth[idx], depth[(*it).ff])-bef+1;
            //cout << (*it).ff << ' ' << chain[idx] << ' ' << bef << '\n';
            ret += cnt*getbit((*it).ss-1);
            updbit((*it).ss, cnt);
            erase.pb((*it).ss);
            if(it == v.begin()) break;
            --it;
        }
        idx = prt[chain[idx]];
    }
    for(auto u : erase)
        updbit(u, -(getbit(u)-getbit(u-1)));
    return ret;
}
void updtree(ll idx, ll val){
    while(idx != 0){
        deque<pll> &v = vec[chain[idx]];
        auto it  = upper_bound(v.begin(), v.end(), mp(idx,ll(1e9)));
        while(it != v.begin())
            v.pop_front();
        v.push_front({idx, val});
        idx = prt[chain[idx]];
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    vector<ll> compress;
    for(int i = 1; i <= n; ++i){
        cin >> val[i];
        compress.pb(val[i]);
    }
    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end())-compress.begin());
    for(int i = 1; i <= n; ++i)
        val[i] = lower_bound(compress.begin(), compress.end(), val[i])-compress.begin();
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        querry.pb(y);
    }
    dfs1(1);
    dfs2(1);
    updtree(1, val[1]);
    for(auto u : querry){
        
        cout << gettree(prt[u]) << '\n';

        updtree(u, val[u]);
    }
}

Compilation message (stderr)

construction.cpp: In function 'int dfs1(int)':
construction.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
construction.cpp: In function 'int dfs2(int)':
construction.cpp:51:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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