Submission #797891

#	Time	Username	Problem	Language	Result	Execution time	Memory
797891		vjudge1	Construction of Highway (JOI18_construction)	C++98	16 / 100	1409 ms	3540 KiB

construction

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fi first
#define se second
#define ll long long
using namespace std ;
using namespace __gnu_pbds ;
const ll N = 1e5 ;
tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> s;
ll ans, c[N + 1], a[N + 1], b[N + 1], dp[N + 1], p[N + 1] ;
vector<ll> now ;
vector<pair<ll, ll>> v[N + 1] ;
void dfs(ll city, ll last, ll abu)
{
    dp[abu] = ans ;
    s.insert({c[city], city}) ;
    ans += s.order_of_key({c[city], 0}) ;
    for(auto i : v[city])
    {
        if(i.fi == last)
            continue ;
        dp[i.se] ;
        dfs(i.fi, city, i.se) ;
    }
    s.erase({c[city], city}) ;
    ans -= s.order_of_key({c[city], 0}) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    ll n ;
    cin >> n ;
    for(ll i = 1 ; i <= n ; i++)
        cin >> c[i] ;
    for(ll i = 1 ; i < n ; i++)
    {
        cin >> a[i] >> b[i] ;
        p[b[i]] = a[i] ;
        v[a[i]].push_back({b[i], i}) ;
        v[b[i]].push_back({a[i], i}) ;
    }
    if(n <= 4000)
    {
        for(ll i = 1 ; i < n ; i++)
        {
            ll num = a[i] ;
            ans = 0 ;
            s.clear() ;
            while(num)
            {
                ans += s.order_of_key({c[num], 0}) ;
                s.insert({c[num], num}) ;
                c[num] = c[b[i]] ;
                num = p[num] ;
            }
            cout << ans << '\n' ;
        }
        return 0 ;
    }
    dfs(1, 0, 0) ;
    for(ll i = 1 ; i < n ; i++)
        cout << dp[i] << '\n' ;
    return 0 ;
}
//s.find_by_order(k); k-й по величине элемент в множестве
//s.order_of_key(x); сколько элементов в множестве меньше

Compilation message (stderr)

construction.cpp: In function 'void dfs(long long int, long long int, long long int)':
construction.cpp:22:16: warning: statement has no effect [-Wunused-value]
   22 |         dp[i.se] ;
      |         ~~~~~~~^

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