Submission #154515

#	Time	Username	Problem	Language	Result	Execution time	Memory
154515		karma	Construction of Highway (JOI18_construction)	C++14	100 / 100	532 ms	107364 KiB

construction

#include<bits/stdc++.h>
#define Task     "test"
#define ll       long long
#define pb       emplace_back
#define mp       make_pair
#define fi       first
#define se       second

using namespace std;

const int N = int(1e5) + 2;
typedef pair<int, int> pii;

int sz[N], head[N], ind[N], pos[N], nChain = 0, nBase = 0;
int n, _a[N], _b[N], c[N], t[N], p[N], bitsz;
vector<int> a[N];
deque<pii> dq[N];

void DFS(int u) {
    sz[u] = 1;
    for(int v: a[u]) DFS(v), sz[u] += sz[v];
}

void HLD(int u) {
     if(!head[nChain]) head[nChain] = u;
     ind[u] = nChain, pos[u] = ++nBase;
     int big = 0;
     for(int v: a[u])
        if(sz[big] < sz[v]) big = v;
     if(big) HLD(big);
     for(int v: a[u]) {
        if(v != big) ++nChain, HLD(v);
     }
}

void Rs(int n) {bitsz = n; fill(t, t + bitsz + 1, 0);}
void Update(int x, int val) {for(; x <= bitsz; x += (x & -x)) t[x] += val;}
int Get(int x) {int res = 0; for(; x > 0; x -= (x & -x)) res += t[x]; return res;}

ll Solve(int par, int u) {
   ll res = 0;
   // Count par
   int uch = ind[par], cnt;
   vector<pii> val, tmp;
   vector<int> idx;
   while(1) {
       cnt = pos[par] - pos[head[uch]] + 1;
       tmp.clear();
       for(int i = 0; i < dq[uch].size(); ++i) {
          if(dq[uch][i].se <= cnt) {
             tmp.pb(dq[uch][i]);
             cnt -= dq[uch][i].se;
          } else {
             tmp.pb(dq[uch][i].fi, cnt);
             break;
          }
       }
       for(int i = int(tmp.size()) - 1; i >= 0; --i) idx.pb(tmp[i].fi), val.pb(tmp[i]);
       if(!uch) break;
       par = p[head[uch]], uch = ind[par];
   }
   sort(idx.begin(), idx.end());
   idx.erase(unique(idx.begin(), idx.end()), idx.end());
   reverse(val.begin(), val.end());
   int cur = 0; Rs(idx.size());
   for(pii p: val) {
      p.fi = lower_bound(idx.begin(), idx.end(), p.fi) - idx.begin() + 1;
      res += 1ll * p.se * (cur - Get(p.fi));
      cur += p.se, Update(p.fi, p.se);
   }
   // Update u
   uch = ind[u]; cur = c[u];
   while(1) {
       cnt = pos[u] - pos[head[uch]] + 1;
       while(dq[uch].size() && cnt) {
          if(dq[uch][0].se <= cnt) {
             cnt -= dq[uch][0].se;
             dq[uch].pop_front();
          } else {
             dq[uch][0].se -= cnt;
             break;
          }
       }
       dq[uch].push_front(mp(cur, pos[u] - pos[head[uch]] + 1));
       if(!uch) break;
       u = p[head[uch]], uch = ind[u];
   }
   return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> c[i];
    for(int i = 1; i < n; ++i) {
        cin >> _a[i] >> _b[i];
        a[_a[i]].pb(_b[i]);
        p[_b[i]] = _a[i];
    }
    DFS(1); HLD(1);
    for(int i = 1; i < n; ++i) cout << Solve(_a[i], _b[i]) << '\n';
}

Compilation message (stderr)

construction.cpp: In function 'long long int Solve(int, int)':
construction.cpp:49:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i = 0; i < dq[uch].size(); ++i) {
                       ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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