Submission #443169

#	Time	Username	Problem	Language	Result	Execution time	Memory
443169		cpp219	Construction of Highway (JOI18_construction)	C++14	100 / 100	448 ms	107880 KiB

construction

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;

vector<ll> g[N];
LL edge[N];
ll n,a[N],x,y,head[N],child[N],par[N],curSZ,d[N];
deque<LL> chain[N];

void DFS_sz(ll u){
    child[u] = 1;
    ll mx = 0;
    for (ll i = 0;i < g[u].size();i++){
        ll v = g[u][i];
        DFS_sz(v); child[u] += child[v];
        if (child[v] > mx) mx = child[v],swap(g[u][0],g[u][i]);
    }
}

void DFS_hld(ll u){
    for (auto i : g[u]){
        par[i] = u; d[i] = d[u] + 1;
        if (i == g[u][0]) head[i] = head[u];
        else head[i] = i; DFS_hld(i);
    }
}

ll bit[N];

void Clear(){
    for (ll i = 1;i <= curSZ;i++) bit[i] = 0;
}

void upd(ll p,ll val){
    for (ll i = p;i <= curSZ;i += i & -i) bit[i] += val;
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}

void AddEdge(ll u,ll val){
    while(u != -1){
        ll nu = head[u],sz = d[u] - d[nu] + 1;
        while(!chain[nu].empty()){
            LL now = chain[nu].front();
            if (sz < now.fs){
                chain[nu].front().fs -= sz;
                break;
            }
            else{
                sz -= now.fs; chain[nu].pop_front();
            }
        }
        chain[nu].push_front({d[u] - d[nu] + 1,val}); u = par[nu];
    }
}

void compress(deque<LL> &v){
    vector<ll> now;
    for (auto i : v) now.push_back(i.sc);
    sort(now.begin(),now.end()); now.resize(unique(now.begin(),now.end()) - now.begin());
    for (ll i = 0;i < v.size();i++){
        ll cur = lower_bound(now.begin(),now.end(),v[i].sc) - now.begin() + 1;
        v[i].sc = cur;
    }
}

void out(deque<LL> dq){
    for (auto i : dq) cout<<i.fs<<" "<<i.sc<<"\n";
    exit(0);
}

ll Query(ll u){
    deque<LL> v; ll root = u;
    while(u != -1){
        vector<LL> tmp;
        ll nu = head[u],sz = d[u] - d[nu] + 1;
        for (auto i : chain[nu]){
            if (!sz) break;
            ll p = min(sz,i.fs);
            sz -= p; tmp.push_back({p,i.sc});
        }
        reverse(tmp.begin(),tmp.end());
        for (auto i : tmp) v.push_front(i);
        u = par[nu];
    }
    reverse(v.begin(),v.end());
    curSZ = v.size(); Clear(); compress(v);
    //if (root == 3){
        //cout<<head[3]; exit(0);
        //out(v);
    //}
    ll ans = 0;
    for (auto i : v){
        upd(i.sc,i.fs); ans += i.fs * Get(i.sc - 1);
    }
    //if (root == 3) cout<<ans;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i];
    for (ll i = 1;i < n;i++){
        cin>>x>>y; edge[i] = {x,y};
        g[x].push_back(y);
    }
    DFS_sz(1); head[1] = 1; DFS_hld(1); par[1] = -1; //cout<<d[4]; return 0;
    chain[1].push_back({1,a[1]});
    for (ll i = 1;i < n;i++){
        cout<<Query(edge[i].fs)<<"\n";
        //Query(edge[i].fs);
        AddEdge(edge[i].sc,a[edge[i].sc]);
        //if (edge[i].sc == 4) out(chain[1]);
    }
}

Compilation message (stderr)

construction.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
construction.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
construction.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
construction.cpp: In function 'void DFS_sz(int)':
construction.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (ll i = 0;i < g[u].size();i++){
      |                   ~~^~~~~~~~~~~~~
construction.cpp: In function 'void DFS_hld(int)':
construction.cpp:35:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   35 |         else head[i] = i; DFS_hld(i);
      |         ^~~~
construction.cpp:35:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   35 |         else head[i] = i; DFS_hld(i);
      |                           ^~~~~~~
construction.cpp: In function 'void compress(std::deque<std::pair<int, int> >&)':
construction.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (ll i = 0;i < v.size();i++){
      |                   ~~^~~~~~~~~~
construction.cpp: In function 'int Query(int)':
construction.cpp:88:21: warning: unused variable 'root' [-Wunused-variable]
   88 |     deque<LL> v; ll root = u;
      |                     ^~~~
construction.cpp: In function 'int main()':
construction.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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