Submission #204632

#	Time	Username	Problem	Language	Result	Execution time	Memory
204632		egekabas	Construction of Highway (JOI18_construction)	C++14	7 / 100	2066 ms	25772 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 dfs1(int v){
    subsz[v] = 1;
    for(auto u : g[v]){
        prt[u] = v;
        dfs1(u);
        subsz[v] += subsz[u];
    }
}
int eul[100009];
int chain[100009];
int 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);
}
struct node{
    map<int, int> mpp;
    int ret = 0;
};
node merge(node n1, node n2){
    node n = node();
    n.ret = n1.ret+n2.ret;
    auto it = n2.mpp.begin();
    int cur = 0;
    for(auto u : n1.mpp){
        while(it != n2.mpp.end() && (*it).ff < u.ff){
            cur += (*it).ss;
            ++it;
        }
        n.ret += cur*u.ss;
    }
    for(auto u : n1.mpp)
        n.mpp[u.ff] += u.ss;
    for(auto u : n2.mpp)
        n.mpp[u.ff] += u.ss;
    
    return n;
}
void mergeref(node &n1, node &n2, node &n){
    n.ret = n1.ret+n2.ret;
    n.mpp.clear();
    auto it = n2.mpp.begin();
    int cur = 0;
    for(auto u : n1.mpp){
        while(it != n2.mpp.end() && (*it).ff < u.ff){
            cur += (*it).ss;
            ++it;
        }
        n.ret += cur*u.ss;
    }
    for(auto u : n1.mpp)
        n.mpp[u.ff] += u.ss;
    for(auto u : n2.mpp)
        n.mpp[u.ff] += u.ss;
}
node seg[400009];
int lazy[400009];
void push(int v, int tl, int tm, int tr){
    if(lazy[v] == 0) return;
    seg[2*v].ret = seg[2*v+1].ret = 0;
    seg[2*v].mpp.clear();
    seg[2*v+1].mpp.clear();
    
    seg[2*v].mpp[lazy[v]] = (tm-tl+1);
    seg[2*v+1].mpp[lazy[v]] = (tr-tm);
        
    lazy[2*v] = lazy[2*v+1] = lazy[v];
    lazy[v] = 0;
}
node get(int v, int tl, int tr, int l, int r){
    if(r < tl || tr < l)
        return node();
    if(l <= tl && tr <= r)
        return seg[v];
    else{
        int tm = (tl+tr)/2;
        push(v, tl, tm, tr);
        return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }
}
void upd(int v, int tl, int tr, int l, int r, int val){
    if(r < tl || tr < l)
        return;
    if(l <= tl && tr <= r){
        lazy[v] = val;
        seg[v].ret = 0;
        seg[v].mpp.clear();
        seg[v].mpp[val] = (tr-tl+1);
    }
    else{
        int tm = (tl+tr)/2;
        push(v, tl, tm, tr);
        upd(2*v, tl, tm, l, r, val);
        upd(2*v+1, tm+1, tr, l, r, val);
        mergeref(seg[2*v], seg[2*v+1], seg[v]);
    }
}
int gettree(int idx){
    node cur = node();
    while(idx != 0){
        cur = merge( get(1, 0, n-1, eul[chain[idx]], eul[idx]) ,cur);
        idx = prt[chain[idx]];
    }
    return cur.ret;
}
void updtree(int idx, int val){
    while(idx != 0){
        upd(1, 0, n-1, eul[chain[idx]], eul[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;
    for(int i = 1; i <= n; ++i)
        cin >> val[i];
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        querry.pb(y);
    }
    dfs1(1);
    dfs2(1);
    for(auto u : querry){
        cout << gettree(u) << '\n';
        updtree(u, val[u]);
    }
}

Compilation message (stderr)

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

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