제출 #204675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204675		egekabas	Construction of Highway (JOI18_construction)	C++14	컴파일 에러	0 ms	0 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 eul[100009];
ll chain[100009];
ll cureul = 0;
ll dfs2(ll v){
    //cout << v << " -- " << cureul << '\n';
    eul[v] = cureul++;
    if(eul[prt[v]] == eul[v]-1)
        chain[v] = chain[prt[v]];
    else
        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)
        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+5){
        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 = v.end();
        --it;
        while(1){
            ll bef = depth[chain[idx]]-1;
            if(it != v.begin())
                bef = depth[(*(it-1)).ff];
            
            ll cnt = min(depth[idx], depth[(*it).ff])-bef;
            if(!cnt){
                --it;
                continue;
            }
            //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]];
    }
}
ll 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';
        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:51:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
construction.cpp: At global scope:
construction.cpp:112:9: error: '::main' must return 'int'
 ll main() {
         ^