oj.uz

Submission #1116941

# Submission time Handle Problem Language Result Execution time Memory
1116941 2024-11-22T15:53:16 Z imarn Construction of Highway (JOI18_construction) C++14
100 / 100
 617 ms 86232 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
ll fw[mxn]{0};
vector<int>tmp;
void add(int i,int amt){
    i=upper_bound(all(tmp),i)-tmp.begin();
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
ll qr(int i,ll rs=0){
    i=upper_bound(all(tmp),i)-tmp.begin();
    for(;i;i-=i&-i)rs+=fw[i];
    return rs;
}
vector<int>g[mxn];
int s[mxn]{0};
int a[mxn],b[mxn],sz[mxn],pr[mxn]{0},head[mxn]{0},id[mxn]{0},cur=0;
void dfs(int u,int p){
    sz[u]=1;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cur;
    int hv=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(hv==-1||sz[hv]<sz[v])hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}
deque<pair<pii,int>>dq[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],tmp.pb(s[i]);
    sort(all(tmp));tmp.erase(unique(all(tmp)),tmp.end());
    for(int i=1;i<=n-1;i++){
        cin>>a[i]>>b[i];g[a[i]].pb(b[i]);g[b[i]].pb(a[i]);
    }dfs(1,-1);hld(1,1,1);dq[1].push_front({{1,1},s[1]});
    for(int i=1;i<=n-1;i++){
        int x=a[i],y=b[i];
        vector<pair<pii,int>>rs;
        stack<pair<pii,int>>st;
        while(x!=-1){
            while(!dq[head[x]].empty()){
                auto it = dq[head[x]].front();
                if(it.f.s<=id[x])st.push(it),dq[head[x]].pop_front();
                else if(it.f.f<=id[x]){
                    dq[head[x]].pop_front();
                    dq[head[x]].push_front({{id[x]+1,it.f.s},it.s});
                    st.push({{it.f.f,id[x]},it.s});
                    break;
                }else break;
            }while(!st.empty())rs.pb(st.top()),st.pop();
            dq[head[x]].push_front({{id[head[x]],id[x]},s[y]});
            x=pr[head[x]];
        }if(dq[head[y]].empty())dq[head[y]].pb({{id[y],id[y]},s[y]});
        else dq[head[y]].back().f.s=id[y],dq[head[y]].back().s=s[y];
        ll ans=0;
        for(auto it : rs)ans+=qr(it.s-1)*(it.f.s-it.f.f+1),add(it.s,it.f.s-it.f.f+1);
        cout<<ans<<'\n';
        for(auto it : rs)add(it.s,-it.f.s+it.f.f-1);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 71240 KB Output is correct
2 Correct 54 ms 71240 KB Output is correct
3 Correct 47 ms 71220 KB Output is correct
4 Correct 51 ms 71296 KB Output is correct
5 Correct 51 ms 71248 KB Output is correct
6 Correct 52 ms 71176 KB Output is correct
7 Correct 46 ms 71248 KB Output is correct
8 Correct 42 ms 71252 KB Output is correct
9 Correct 41 ms 71180 KB Output is correct
10 Correct 42 ms 71256 KB Output is correct
11 Correct 44 ms 71248 KB Output is correct
12 Correct 48 ms 71288 KB Output is correct
13 Correct 48 ms 71392 KB Output is correct
14 Correct 51 ms 71304 KB Output is correct
15 Correct 53 ms 71240 KB Output is correct
16 Correct 52 ms 71396 KB Output is correct
17 Correct 52 ms 71260 KB Output is correct
18 Correct 58 ms 71240 KB Output is correct
19 Correct 47 ms 71240 KB Output is correct
20 Correct 46 ms 71252 KB Output is correct
21 Correct 56 ms 71240 KB Output is correct
22 Correct 55 ms 71248 KB Output is correct
23 Correct 50 ms 71168 KB Output is correct
24 Correct 49 ms 71240 KB Output is correct
25 Correct 47 ms 71168 KB Output is correct
26 Correct 48 ms 71240 KB Output is correct
27 Correct 48 ms 71240 KB Output is correct
28 Correct 51 ms 71248 KB Output is correct
29 Correct 47 ms 71532 KB Output is correct
30 Correct 51 ms 71180 KB Output is correct
31 Correct 54 ms 71200 KB Output is correct
32 Correct 52 ms 71240 KB Output is correct
33 Correct 56 ms 71248 KB Output is correct
34 Correct 48 ms 71336 KB Output is correct
35 Correct 55 ms 71152 KB Output is correct
36 Correct 44 ms 71248 KB Output is correct
37 Correct 47 ms 71136 KB Output is correct
38 Correct 51 ms 71240 KB Output is correct
39 Correct 47 ms 71236 KB Output is correct
40 Correct 46 ms 71256 KB Output is correct
41 Correct 47 ms 71140 KB Output is correct
42 Correct 53 ms 71240 KB Output is correct
43 Correct 53 ms 71188 KB Output is correct
44 Correct 46 ms 71248 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 71240 KB Output is correct
2 Correct 54 ms 71240 KB Output is correct
3 Correct 47 ms 71220 KB Output is correct
4 Correct 51 ms 71296 KB Output is correct
5 Correct 51 ms 71248 KB Output is correct
6 Correct 52 ms 71176 KB Output is correct
7 Correct 46 ms 71248 KB Output is correct
8 Correct 42 ms 71252 KB Output is correct
9 Correct 41 ms 71180 KB Output is correct
10 Correct 42 ms 71256 KB Output is correct
11 Correct 44 ms 71248 KB Output is correct
12 Correct 48 ms 71288 KB Output is correct
13 Correct 48 ms 71392 KB Output is correct
14 Correct 51 ms 71304 KB Output is correct
15 Correct 53 ms 71240 KB Output is correct
16 Correct 52 ms 71396 KB Output is correct
17 Correct 52 ms 71260 KB Output is correct
18 Correct 58 ms 71240 KB Output is correct
19 Correct 47 ms 71240 KB Output is correct
20 Correct 46 ms 71252 KB Output is correct
21 Correct 56 ms 71240 KB Output is correct
22 Correct 55 ms 71248 KB Output is correct
23 Correct 50 ms 71168 KB Output is correct
24 Correct 49 ms 71240 KB Output is correct
25 Correct 47 ms 71168 KB Output is correct
26 Correct 48 ms 71240 KB Output is correct
27 Correct 48 ms 71240 KB Output is correct
28 Correct 51 ms 71248 KB Output is correct
29 Correct 47 ms 71532 KB Output is correct
30 Correct 51 ms 71180 KB Output is correct
31 Correct 54 ms 71200 KB Output is correct
32 Correct 52 ms 71240 KB Output is correct
33 Correct 56 ms 71248 KB Output is correct
34 Correct 48 ms 71336 KB Output is correct
35 Correct 55 ms 71152 KB Output is correct
36 Correct 44 ms 71248 KB Output is correct
37 Correct 47 ms 71136 KB Output is correct
38 Correct 51 ms 71240 KB Output is correct
39 Correct 47 ms 71236 KB Output is correct
40 Correct 46 ms 71256 KB Output is correct
41 Correct 47 ms 71140 KB Output is correct
42 Correct 53 ms 71240 KB Output is correct
43 Correct 53 ms 71188 KB Output is correct
44 Correct 46 ms 71248 KB Output is correct
45 Correct 52 ms 71240 KB Output is correct
46 Correct 52 ms 71532 KB Output is correct
47 Correct 52 ms 71632 KB Output is correct
48 Correct 51 ms 71752 KB Output is correct
49 Correct 49 ms 71888 KB Output is correct
50 Correct 47 ms 71752 KB Output is correct
51 Correct 43 ms 71884 KB Output is correct
52 Correct 52 ms 71716 KB Output is correct
53 Correct 48 ms 71752 KB Output is correct
54 Correct 44 ms 71752 KB Output is correct
55 Correct 48 ms 71648 KB Output is correct
56 Correct 49 ms 71496 KB Output is correct
57 Correct 54 ms 71852 KB Output is correct
58 Correct 57 ms 72008 KB Output is correct
59 Correct 65 ms 72008 KB Output is correct
60 Correct 74 ms 71968 KB Output is correct
61 Correct 57 ms 71484 KB Output is correct
62 Correct 54 ms 71496 KB Output is correct
63 Correct 66 ms 72108 KB Output is correct
64 Correct 58 ms 71520 KB Output is correct
65 Correct 54 ms 71504 KB Output is correct
66 Correct 58 ms 71728 KB Output is correct
67 Correct 57 ms 71504 KB Output is correct
68 Correct 49 ms 71752 KB Output is correct
69 Correct 55 ms 71572 KB Output is correct
70 Correct 51 ms 71680 KB Output is correct
71 Correct 47 ms 71456 KB Output is correct
72 Correct 72 ms 71980 KB Output is correct
73 Correct 60 ms 71908 KB Output is correct
74 Correct 51 ms 71496 KB Output is correct
75 Correct 67 ms 71512 KB Output is correct
76 Correct 55 ms 71568 KB Output is correct
77 Correct 52 ms 71544 KB Output is correct
78 Correct 49 ms 71512 KB Output is correct
79 Correct 48 ms 71580 KB Output is correct
80 Correct 64 ms 71500 KB Output is correct
81 Correct 62 ms 71428 KB Output is correct
82 Correct 63 ms 71504 KB Output is correct
83 Correct 51 ms 71604 KB Output is correct
84 Correct 60 ms 71572 KB Output is correct
85 Correct 49 ms 71508 KB Output is correct
86 Correct 46 ms 71496 KB Output is correct

Subtask #3
84.0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 71240 KB Output is correct
2 Correct 54 ms 71240 KB Output is correct
3 Correct 47 ms 71220 KB Output is correct
4 Correct 51 ms 71296 KB Output is correct
5 Correct 51 ms 71248 KB Output is correct
6 Correct 52 ms 71176 KB Output is correct
7 Correct 46 ms 71248 KB Output is correct
8 Correct 42 ms 71252 KB Output is correct
9 Correct 41 ms 71180 KB Output is correct
10 Correct 42 ms 71256 KB Output is correct
11 Correct 44 ms 71248 KB Output is correct
12 Correct 48 ms 71288 KB Output is correct
13 Correct 48 ms 71392 KB Output is correct
14 Correct 51 ms 71304 KB Output is correct
15 Correct 53 ms 71240 KB Output is correct
16 Correct 52 ms 71396 KB Output is correct
17 Correct 52 ms 71260 KB Output is correct
18 Correct 58 ms 71240 KB Output is correct
19 Correct 47 ms 71240 KB Output is correct
20 Correct 46 ms 71252 KB Output is correct
21 Correct 56 ms 71240 KB Output is correct
22 Correct 55 ms 71248 KB Output is correct
23 Correct 50 ms 71168 KB Output is correct
24 Correct 49 ms 71240 KB Output is correct
25 Correct 47 ms 71168 KB Output is correct
26 Correct 48 ms 71240 KB Output is correct
27 Correct 48 ms 71240 KB Output is correct
28 Correct 51 ms 71248 KB Output is correct
29 Correct 47 ms 71532 KB Output is correct
30 Correct 51 ms 71180 KB Output is correct
31 Correct 54 ms 71200 KB Output is correct
32 Correct 52 ms 71240 KB Output is correct
33 Correct 56 ms 71248 KB Output is correct
34 Correct 48 ms 71336 KB Output is correct
35 Correct 55 ms 71152 KB Output is correct
36 Correct 44 ms 71248 KB Output is correct
37 Correct 47 ms 71136 KB Output is correct
38 Correct 51 ms 71240 KB Output is correct
39 Correct 47 ms 71236 KB Output is correct
40 Correct 46 ms 71256 KB Output is correct
41 Correct 47 ms 71140 KB Output is correct
42 Correct 53 ms 71240 KB Output is correct
43 Correct 53 ms 71188 KB Output is correct
44 Correct 46 ms 71248 KB Output is correct
45 Correct 52 ms 71240 KB Output is correct
46 Correct 52 ms 71532 KB Output is correct
47 Correct 52 ms 71632 KB Output is correct
48 Correct 51 ms 71752 KB Output is correct
49 Correct 49 ms 71888 KB Output is correct
50 Correct 47 ms 71752 KB Output is correct
51 Correct 43 ms 71884 KB Output is correct
52 Correct 52 ms 71716 KB Output is correct
53 Correct 48 ms 71752 KB Output is correct
54 Correct 44 ms 71752 KB Output is correct
55 Correct 48 ms 71648 KB Output is correct
56 Correct 49 ms 71496 KB Output is correct
57 Correct 54 ms 71852 KB Output is correct
58 Correct 57 ms 72008 KB Output is correct
59 Correct 65 ms 72008 KB Output is correct
60 Correct 74 ms 71968 KB Output is correct
61 Correct 57 ms 71484 KB Output is correct
62 Correct 54 ms 71496 KB Output is correct
63 Correct 66 ms 72108 KB Output is correct
64 Correct 58 ms 71520 KB Output is correct
65 Correct 54 ms 71504 KB Output is correct
66 Correct 58 ms 71728 KB Output is correct
67 Correct 57 ms 71504 KB Output is correct
68 Correct 49 ms 71752 KB Output is correct
69 Correct 55 ms 71572 KB Output is correct
70 Correct 51 ms 71680 KB Output is correct
71 Correct 47 ms 71456 KB Output is correct
72 Correct 72 ms 71980 KB Output is correct
73 Correct 60 ms 71908 KB Output is correct
74 Correct 51 ms 71496 KB Output is correct
75 Correct 67 ms 71512 KB Output is correct
76 Correct 55 ms 71568 KB Output is correct
77 Correct 52 ms 71544 KB Output is correct
78 Correct 49 ms 71512 KB Output is correct
79 Correct 48 ms 71580 KB Output is correct
80 Correct 64 ms 71500 KB Output is correct
81 Correct 62 ms 71428 KB Output is correct
82 Correct 63 ms 71504 KB Output is correct
83 Correct 51 ms 71604 KB Output is correct
84 Correct 60 ms 71572 KB Output is correct
85 Correct 49 ms 71508 KB Output is correct
86 Correct 46 ms 71496 KB Output is correct
87 Correct 74 ms 72264 KB Output is correct
88 Correct 122 ms 74568 KB Output is correct
89 Correct 367 ms 82400 KB Output is correct
90 Correct 349 ms 82624 KB Output is correct
91 Correct 386 ms 82524 KB Output is correct
92 Correct 167 ms 85696 KB Output is correct
93 Correct 144 ms 85556 KB Output is correct
94 Correct 156 ms 85696 KB Output is correct
95 Correct 138 ms 83136 KB Output is correct
96 Correct 170 ms 83396 KB Output is correct
97 Correct 166 ms 83392 KB Output is correct
98 Correct 158 ms 83392 KB Output is correct
99 Correct 143 ms 81960 KB Output is correct
100 Correct 398 ms 85696 KB Output is correct
101 Correct 574 ms 86232 KB Output is correct
102 Correct 617 ms 86208 KB Output is correct
103 Correct 576 ms 86208 KB Output is correct
104 Correct 157 ms 81896 KB Output is correct
105 Correct 160 ms 81724 KB Output is correct
106 Correct 167 ms 81856 KB Output is correct
107 Correct 210 ms 81012 KB Output is correct
108 Correct 270 ms 81088 KB Output is correct
109 Correct 339 ms 81600 KB Output is correct
110 Correct 119 ms 84212 KB Output is correct
111 Correct 137 ms 83136 KB Output is correct
112 Correct 143 ms 82100 KB Output is correct
113 Correct 134 ms 80464 KB Output is correct
114 Correct 412 ms 85776 KB Output is correct
115 Correct 383 ms 84720 KB Output is correct
116 Correct 139 ms 80576 KB Output is correct
117 Correct 161 ms 79552 KB Output is correct
118 Correct 157 ms 78844 KB Output is correct
119 Correct 183 ms 78528 KB Output is correct
120 Correct 128 ms 78308 KB Output is correct
121 Correct 124 ms 77760 KB Output is correct
122 Correct 129 ms 77556 KB Output is correct
123 Correct 158 ms 79552 KB Output is correct
124 Correct 159 ms 78828 KB Output is correct
125 Correct 163 ms 78528 KB Output is correct
126 Correct 145 ms 78524 KB Output is correct
127 Correct 129 ms 77868 KB Output is correct
128 Correct 131 ms 77448 KB Output is correct