Submission #1064533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064533		phong	Construction of Highway (JOI18_construction)	C++17	100 / 100	405 ms	31948 KiB

construction

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, c[nmax];
pii a[nmax];
int sz[nmax], par[nmax];
vector<int> adj[nmax];

void dfs(int u, int p){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        par[v] = u;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
int head[nmax], ind[nmax], pos[nmax], Time = 0, nchain = 1;
int rev[nmax];

void dfs_2(int u, int p){
    if(!head[nchain]) head[nchain] = u;
    pos[u] = ++Time;
    ind[u] = nchain;
    rev[Time] = u;
    int idx =-1;
    for(auto v : adj[u]){
        if(v == p) continue;
        if(idx == -1 || sz[idx] < sz[v]){
            idx = v;
        }
    }
    if(idx != -1) dfs_2(idx, u);
    for(auto v : adj[u]){
        if(v == p) continue;
        if(idx == v) continue;
        ++nchain;
        dfs_2(v, u);
    }
}
vector<pii> one;
struct Seg{
    int ma[1 << 18], mi[1 << 18], lz[1 << 18];
    void combine(int id){
        ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
        mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
    }
    void build(int id, int l, int r){
        lz[id] = -1;
        if(l == r){
            ma[id] = mi[id] = c[rev[l]];
            return;
        }
        int mid = r+ l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        combine(id);
    }
    void fix(int id, int val){
        if(val == -1) return;
        ma[id] = val;
        mi[id] = val;
        lz[id] = val;
    }
    void down(int id){
        fix(id << 1, lz[id]);
        fix(id << 1| 1, lz[id]);
        lz[id] = -1;
    }
    void update(int id, int l, int r, int u, int v, int val){
        if(l > v || r < u) return;
        if(l >= u && r <= v) return fix(id, val);
        down(id);
        int mid = r + l >> 1;
        update(id << 1, l, mid, u, v,val);
        update(id << 1 | 1, mid + 1, r, u, v,val);
        combine(id);
    }
    void get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return;
        if(l >= u && r <= v && ma[id] == mi[id]){
            one.push_back({r - l + 1, ma[id]});
            return;
        }
        down(id);
        int mid = r + l >> 1;
        get(id << 1 | 1, mid + 1, r, u, v);
        get(id << 1, l, mid, u, v);
    }
    int Find(int id, int l, int r, int u){
        if(l == r) return ma[id];
        down(id);
        int mid = r + l >> 1;
        if(mid < u) return Find(id << 1 | 1, mid + 1, r, u);
        else return Find(id << 1,l,mid, u);
    }
}tree;
struct FEN{
    ll f[nmax];
    vector<int> tmp;
    void update(int x, int val){
        for(; x <= n; x += x&-x) f[x] += val, tmp.push_back(x);
    }
    ll get(int x){
        ll cur = 0;
        for(; x; x -= x&-x) cur += f[x];
        return cur;
    }
    void clear(){
        for(auto p : tmp) f[p] = 0;
        tmp.clear();
    }
}F;
ll calc(int u, int x){
    int A = u;
    int uchain = ind[u];
    one.clear();
    while(1){
        if(uchain == 1){
            tree.get(1, 1, n, pos[1], pos[u]);
            tree.update(1, 1, n, pos[1], pos[u], c[x]);
            break;
        }
        tree.get(1, 1, n, pos[head[uchain]], pos[u]);
        tree.update(1, 1, n, pos[head[uchain]], pos[u], c[x]);
        u = par[head[uchain]];
        uchain = ind[u];
    }
    ll ans = 0;
//    cout << A << ' ' << x << "#"<< ' ' << c[x] << endl;
//    for(int i = 1; i <= n; ++i) cout << tree.Find(1, 1, n, pos[i]) << ' ';
//    cout << endl;
    for(auto [x, y] : one){
        ans += 1ll * F.get(y - 1) * x;
        F.update(y, x);
//        cout << x << ' ' << y << endl;
    }
    F.clear();
    return ans;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    vector<int> nen;
    for(int i = 1; i <= n; ++i) cin >> c[i],nen.push_back(c[i]);
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for(int i = 1; i <= n; ++i) c[i] = lower_bound(nen.begin(), nen.end(),c[i]) - nen.begin() + 1;
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> a[i].fi >> a[i].se;
        adj[a[i].fi].push_back(a[i].se);
    }
    dfs(1, -1);
    dfs_2(1, -1);
//    for(int i = 1; i <= n; ++i) cout << c[i] << ' ';
    tree.build(1, 1, n);
//    for(int i = 1; i <= n; ++i) cout << tree.Find(1, 1, n, pos[i]) << ' ';
//    ll ans = 0;
    for(int i = 1; i < n; ++i){
        int x = a[i].fi, y = a[i].se;
//        calc(x, y);
       cout <<  calc(x, y) << endl;
    }
}
/*

*/

Compilation message (stderr)

construction.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
construction.cpp:66:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int mid = r+ l >> 1;
      |                   ~^~~
construction.cpp: In member function 'void Seg::update(long long int, long long int, long long int, long long int, long long int, long long int)':
construction.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = r + l >> 1;
      |                   ~~^~~
construction.cpp: In member function 'void Seg::get(long long int, long long int, long long int, long long int, long long int)':
construction.cpp:98:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |         int mid = r + l >> 1;
      |                   ~~^~~
construction.cpp: In member function 'long long int Seg::Find(long long int, long long int, long long int, long long int)':
construction.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid = r + l >> 1;
      |                   ~~^~~
construction.cpp: In function 'long long int calc(long long int, long long int)':
construction.cpp:127:9: warning: unused variable 'A' [-Wunused-variable]
  127 |     int A = u;
      |         ^
construction.cpp: At global scope:
construction.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main(){
      | ^~~~
construction.cpp: In function 'int main()':
construction.cpp:165:13: warning: unused variable 'x' [-Wunused-variable]
  165 |         int x, y;
      |             ^
construction.cpp:165:16: warning: unused variable 'y' [-Wunused-variable]
  165 |         int x, y;
      |                ^

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