oj.uz

Submission #797889

# Submission time Handle Problem Language Result Execution time Memory
797889 2023-07-30T05:05:26 Z vjudge1 Construction of Highway (JOI18_construction) C++
7 / 100
 18 ms 3028 KB 
#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 <= 2000)
    {
        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 ;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2716 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 17 ms 2644 KB Output is correct
9 Correct 17 ms 2644 KB Output is correct
10 Correct 17 ms 2644 KB Output is correct
11 Correct 9 ms 2644 KB Output is correct
12 Correct 9 ms 2772 KB Output is correct
13 Correct 9 ms 2768 KB Output is correct
14 Correct 9 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 9 ms 2764 KB Output is correct
20 Correct 9 ms 2644 KB Output is correct
21 Correct 9 ms 2772 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 18 ms 2748 KB Output is correct
27 Correct 9 ms 2768 KB Output is correct
28 Correct 9 ms 2768 KB Output is correct
29 Correct 9 ms 2772 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 9 ms 2644 KB Output is correct
33 Correct 5 ms 2644 KB Output is correct
34 Correct 3 ms 2644 KB Output is correct
35 Correct 3 ms 2644 KB Output is correct
36 Correct 5 ms 2644 KB Output is correct
37 Correct 3 ms 2644 KB Output is correct
38 Correct 3 ms 2644 KB Output is correct
39 Correct 5 ms 2644 KB Output is correct
40 Correct 4 ms 2644 KB Output is correct
41 Correct 3 ms 2644 KB Output is correct
42 Correct 5 ms 2644 KB Output is correct
43 Correct 4 ms 2644 KB Output is correct
44 Correct 3 ms 2644 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2716 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 17 ms 2644 KB Output is correct
9 Correct 17 ms 2644 KB Output is correct
10 Correct 17 ms 2644 KB Output is correct
11 Correct 9 ms 2644 KB Output is correct
12 Correct 9 ms 2772 KB Output is correct
13 Correct 9 ms 2768 KB Output is correct
14 Correct 9 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 9 ms 2764 KB Output is correct
20 Correct 9 ms 2644 KB Output is correct
21 Correct 9 ms 2772 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 18 ms 2748 KB Output is correct
27 Correct 9 ms 2768 KB Output is correct
28 Correct 9 ms 2768 KB Output is correct
29 Correct 9 ms 2772 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 9 ms 2644 KB Output is correct
33 Correct 5 ms 2644 KB Output is correct
34 Correct 3 ms 2644 KB Output is correct
35 Correct 3 ms 2644 KB Output is correct
36 Correct 5 ms 2644 KB Output is correct
37 Correct 3 ms 2644 KB Output is correct
38 Correct 3 ms 2644 KB Output is correct
39 Correct 5 ms 2644 KB Output is correct
40 Correct 4 ms 2644 KB Output is correct
41 Correct 3 ms 2644 KB Output is correct
42 Correct 5 ms 2644 KB Output is correct
43 Correct 4 ms 2644 KB Output is correct
44 Correct 3 ms 2644 KB Output is correct
45 Correct 3 ms 2772 KB Output is correct
46 Incorrect 3 ms 3028 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2716 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 17 ms 2644 KB Output is correct
9 Correct 17 ms 2644 KB Output is correct
10 Correct 17 ms 2644 KB Output is correct
11 Correct 9 ms 2644 KB Output is correct
12 Correct 9 ms 2772 KB Output is correct
13 Correct 9 ms 2768 KB Output is correct
14 Correct 9 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 9 ms 2764 KB Output is correct
20 Correct 9 ms 2644 KB Output is correct
21 Correct 9 ms 2772 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 18 ms 2748 KB Output is correct
27 Correct 9 ms 2768 KB Output is correct
28 Correct 9 ms 2768 KB Output is correct
29 Correct 9 ms 2772 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 9 ms 2644 KB Output is correct
33 Correct 5 ms 2644 KB Output is correct
34 Correct 3 ms 2644 KB Output is correct
35 Correct 3 ms 2644 KB Output is correct
36 Correct 5 ms 2644 KB Output is correct
37 Correct 3 ms 2644 KB Output is correct
38 Correct 3 ms 2644 KB Output is correct
39 Correct 5 ms 2644 KB Output is correct
40 Correct 4 ms 2644 KB Output is correct
41 Correct 3 ms 2644 KB Output is correct
42 Correct 5 ms 2644 KB Output is correct
43 Correct 4 ms 2644 KB Output is correct
44 Correct 3 ms 2644 KB Output is correct
45 Correct 3 ms 2772 KB Output is correct
46 Incorrect 3 ms 3028 KB Output isn't correct
47 Halted 0 ms 0 KB -