제출 #204685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204685		egekabas	Construction of Highway (JOI18_construction)	C++14	0 / 100	55 ms	70008 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<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n;
vector<ll> querry;
ll val[100009];
vector<ll> g[100009];
ll prt[100009];
ll subsz[100009];
ll depth[100009];
ll dfs1(ll v){
    subsz[v] = 1;
    for(auto u : g[v]){
        prt[u] = v;
        depth[u] = depth[v]+1;
        dfs1(u);
        subsz[v] += subsz[u];
    }
}
ll chain[100009];
ll dfs2(ll v){
    //cout << v << " -- " << cureul << '\n';
    if(chain[v] == 0)
        chain[v] = v;
    ll biggest = 0, id = 0;
    for(auto u : g[v])
        if(subsz[u] > biggest){
            biggest = subsz[u];
            id = u;
        }
    if(id != 0){
        chain[id] = chain[v];
        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;
    set<ll> erase;
    while(idx != 0){
        deque<pll> &v = vec[chain[idx]];
        
        auto it = v.end();
        --it;
        while(1){
            //if(it != v.begin() && depth[(*(it-1)).ff] >= depth[idx])
            //    --it;
            ll bef = depth[chain[idx]]-1;
            if(it != v.begin())
                bef = depth[(*(it-1)).ff];
            
            ll cnt = min(depth[idx], depth[(*it).ff])-bef;
            //cout << (*it).ff << ' ' << chain[idx] << ' ' << bef << '\n';
            ret += cnt*getbit((*it).ss-1);
            updbit((*it).ss, cnt);
            erase.insert((*it).ss);
            if(it == v.begin()) break;
            --it;
        }
        idx = prt[chain[idx]];
    }
    for(auto u : erase)
        updbit(u, -(getbit(u)));
    return ret;
}
void updtree(ll idx, ll val){
    while(idx != 0){
        deque<pll> &v = vec[chain[idx]];
        while(!v.empty() && depth[v.front().ff] <= depth[idx])
            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(ll 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(ll i = 1; i <= n; ++i)
        val[i] = lower_bound(compress.begin(), compress.end(), val[i])-compress.begin();
    for(ll i = 1; i < n; ++i){
        ll 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';
        for(int i = 1; i <= n; ++i)
            assert(bit[i] == 0);
        updtree(u, val[u]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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