Submission #468444

#	Time	Username	Problem	Language	Result	Execution time	Memory
468444		Killer2501	Construction of Highway (JOI18_construction)	C++14	100 / 100	454 ms	164692 KiB

construction

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "262144"
#define pll pair<ll, ll>
#define pi pair<ll, pll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e9+7;
const ll N = 2e5+5;
const int base = 350;
const int base2 = 311;
ll n, m, t, k, T, ans, tong, a[N], b[N], c[N], d[N], par[N], fe[N], P[N][19], h[N], cnt, in[N], top[N], nchain[N], chain;
vector<ll> adj[N];
vector<pll> kq;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
string s[N];
void add(ll id, ll x)
{
    for(; id <= m; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
    ll total = 0;
    for(; id; id -= id & -id)total += fe[id];
    return total;
}
void dfs(ll u)
{
    d[u] = 1;
    for(ll v : adj[u])
    {
        h[v] = h[u] + 1;
        par[v] = u;
        dfs(v);
        d[u] += d[v];
    }
}
void hld(ll u)
{
    if(!top[chain])top[chain] = u;
    nchain[u] = chain;
    ll big = -1;
    for(ll v: adj[u])
    {
        if(big == -1 || d[v] > d[big])big = v;
    }
    if(big != -1)hld(big);
    for(ll v: adj[u])
    {
        if(v == big)continue;
        ++chain;
        hld(v);
    }
}
deque<pll> st[N];
void fixv()
{
    vector<ll> vi;
    for(pll x: kq)vi.pb(x.se);
    sort(vi.begin(), vi.end());
    vi.erase(unique(vi.begin(), vi.end()), vi.end());
    for(int i = 0; i < kq.size(); i ++)kq[i].se = lower_bound(vi.begin(), vi.end(), kq[i].se)-vi.begin()+1;
    m = vi.size();
}
ll query(ll u, ll val)
{
    //cout << st[nchain[1]].back().se << '\n';
    ll r = u;
    while(u)
    {
        k = nchain[u];
        ll sz = h[u] - h[top[k]] + 1;
        vector<pll> vi;
        while(sz)
        {
            t = min(sz, st[k][0].fi);
            sz -= t;
            vi.pb({t, st[k][0].se});
            //if(u == 1)cout << t << " " << st[k][i].se <<'\n';
            if(t == st[k][0].fi)st[k].pop_front();
            else st[k][0].fi -= t;
        }
        st[k].push_front({h[u] - h[top[k]] + 1, val});
        while(!vi.empty())
        {
            kq.pb(vi.back());
            vi.pop_back();
        }
        u = par[top[k]];
    }
    //cout << r << '\n';
    //for(pll x: kq)cout << x.fi <<" "<<x.se<<'\n';
    fixv();
    ans = 0;
    for(pll x : kq)
    {

        ans += x.fi * get(x.se-1);
        add(x.se, x.fi);
    }
    fill_n(fe, m+1, 0);
    kq.clear();
    return ans;
}
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> c[i];
    for(int i = 1; i < n; i ++)
    {
        cin >> a[i] >> b[i];
        adj[a[i]].pb(b[i]);
    }
    dfs(1);
    hld(1);
    st[nchain[1]].pb({1, c[1]});
    for(int i = 1; i < n; i ++)
    {
        cout << query(a[i], c[b[i]]) << '\n';
        k = nchain[b[i]];
        if(!st[k].empty() && st[k].back().se == c[b[i]])
        {
            st[k][st[k].size()-1].fi += 1;
            //cout << "same" << '\n';
        }
        else
        {
            //cout << k << " diff" << '\n';
            st[k].pb({1, c[b[i]]});
        }
    }
}
int main()
{
    if(fopen(task".in", "r"))
    {
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
1
5
acbac
7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky

*/

Compilation message (stderr)

construction.cpp: In function 'void fixv()':
construction.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < kq.size(); i ++)kq[i].se = lower_bound(vi.begin(), vi.end(), kq[i].se)-vi.begin()+1;
      |                    ~~^~~~~~~~~~~
construction.cpp: In function 'long long int query(long long int, long long int)':
construction.cpp:80:8: warning: unused variable 'r' [-Wunused-variable]
   80 |     ll r = u;
      |        ^
construction.cpp: In function 'int main()':
construction.cpp:149:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:150:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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