oj.uz

Submission #246358

# Submission time Handle Problem Language Result Execution time Memory
246358 2020-07-08T21:12:37 Z fivefourthreeone Construction of Highway (JOI18_construction) C++17
0 / 100
 40 ms 4096 KB 
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 100001;
int n;
int cnt = 0;
ttgl inout[mxN];
ttgl edges[mxN];
set<int> stt;
map<int, int> mp;
int arr[mxN];
int seg[4*mxN];
int par[mxN][18];
vector<int> adj[mxN];
void upd(int p, int val) {
    for(seg[p+=2*n] = val; p>1; p>>=1) seg[p>>1] = max(seg[p], seg[p^1]);
}
int qmax(int l, int r) {
    int res = 0;
    r++;
    for(l+=2*n, r+=2*n; l<r; l>>=1, r>>=1) {
        if(l&1) res= max(res, seg[l++]);
        if(r&1) res = max(res, seg[--r]);
    }
    return res;
}
int BIT[mxN];
void add(int i, int val) {
    while(i<=n) {
        BIT[i]+= val;
        i +=i&-i;
    }
}
void del(int i) {
    while(i<=n) {
        BIT[i] = 0;
        i +=i&-i;
    }
}
int sum (int i) {
    int res = 0;
    while(i>0) {
        res+=BIT[i];
        i-=i&-i;
    }
    return res;
}
void dfs(int u, int p) {
    par[u][0] = p;
    inout[u].first = cnt++;
    for(int v: adj[u]) {
        if(v==p)continue;
        dfs(v, u);
    }
    inout[u].second = cnt++;
}
int query(int k) {
    //cout<<"\n";
    //cout<<k<<" "<<inout[k].first<<" "<<inout[k].second<<" "<<qmax(inout[k].first, inout[k].second)<<" hi\n";
    return qmax(inout[k].first, inout[k].second);
}
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    owo(i, 0, n) {
        cin>>arr[i];
        stt.insert(arr[i]);
    }
    int idx = 0;
    auto it = stt.begin();
    while(it!=stt.end()) {
        mp[*it] = idx++;
        it++;
    }
    owo(i, 0, n) {
        arr[i] = mp[arr[i]];
    }
    owo(i, 0, n-1) {
        cin>>edges[i].first>>edges[i].second;
        edges[i].first--;
        edges[i].second--;
        adj[edges[i].first].senpai(edges[i].second);
        adj[edges[i].second].senpai(edges[i].first);
    }
    dfs(0, -1);
    owo(lg, 1, 18) {
        owo(i, 0, n) {
            if(par[i][lg-1]==-1) {
                par[i][lg] = -1;
            }else {
                par[i][lg] = par[par[i][lg-1]][lg-1];
            }
        }
    }
    owo(i, 0, 2*mxN) {
        seg[i] = -1;
    }
    upd(inout[0].first, 0);
    owo(i, 1, n) {
        int a = edges[i-1].first;
        int b = edges[i-1].second;
        int ans = 0;
        vector<int> path;
        //cout<<i<<"\n";
        int val = query(a)==0 ? arr[a] : arr[edges[query(a)-1].second];
        while(a!=-1) {
            int num= 1;
            //cout<<a<<" ";
            uwu(i, 18, 0) {
                if(par[a][i]!=-1&&query(par[a][i])==query(a)) {
                    a = par[a][i];
                    num+=(1<<i);
                }
            }
            //cout<<a<<" "<<num<<" "<<val<<" "<<sum(val+1)<<"\n";
            ans+=num*sum(val+1);
            add(val+1, num);
            path.senpai(val+1);
            a = par[a][0];
            val = arr[edges[query(a)-1].second];
            //cout<<query(a)<<"\n";
        }
        owo(i, 0, mxN) {
            BIT[i] = 0;
        }
        cout<<ans<<"\n";
        upd(inout[b].first, i);
        //cout<<inout[b].first<<" "<<i<<" cool\n";
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3968 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 11 ms 3968 KB Output is correct
4 Correct 19 ms 3968 KB Output is correct
5 Correct 30 ms 3968 KB Output is correct
6 Correct 40 ms 3968 KB Output is correct
7 Correct 27 ms 3968 KB Output is correct
8 Correct 38 ms 4096 KB Output is correct
9 Correct 28 ms 4096 KB Output is correct
10 Correct 27 ms 3968 KB Output is correct
11 Correct 26 ms 3968 KB Output is correct
12 Correct 27 ms 4088 KB Output is correct
13 Correct 28 ms 3968 KB Output is correct
14 Correct 30 ms 4096 KB Output is correct
15 Correct 29 ms 3968 KB Output is correct
16 Correct 31 ms 3968 KB Output is correct
17 Correct 28 ms 3968 KB Output is correct
18 Correct 29 ms 3968 KB Output is correct
19 Correct 28 ms 3968 KB Output is correct
20 Correct 28 ms 3968 KB Output is correct
21 Correct 32 ms 4088 KB Output is correct
22 Incorrect 27 ms 3968 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3968 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 11 ms 3968 KB Output is correct
4 Correct 19 ms 3968 KB Output is correct
5 Correct 30 ms 3968 KB Output is correct
6 Correct 40 ms 3968 KB Output is correct
7 Correct 27 ms 3968 KB Output is correct
8 Correct 38 ms 4096 KB Output is correct
9 Correct 28 ms 4096 KB Output is correct
10 Correct 27 ms 3968 KB Output is correct
11 Correct 26 ms 3968 KB Output is correct
12 Correct 27 ms 4088 KB Output is correct
13 Correct 28 ms 3968 KB Output is correct
14 Correct 30 ms 4096 KB Output is correct
15 Correct 29 ms 3968 KB Output is correct
16 Correct 31 ms 3968 KB Output is correct
17 Correct 28 ms 3968 KB Output is correct
18 Correct 29 ms 3968 KB Output is correct
19 Correct 28 ms 3968 KB Output is correct
20 Correct 28 ms 3968 KB Output is correct
21 Correct 32 ms 4088 KB Output is correct
22 Incorrect 27 ms 3968 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3968 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 11 ms 3968 KB Output is correct
4 Correct 19 ms 3968 KB Output is correct
5 Correct 30 ms 3968 KB Output is correct
6 Correct 40 ms 3968 KB Output is correct
7 Correct 27 ms 3968 KB Output is correct
8 Correct 38 ms 4096 KB Output is correct
9 Correct 28 ms 4096 KB Output is correct
10 Correct 27 ms 3968 KB Output is correct
11 Correct 26 ms 3968 KB Output is correct
12 Correct 27 ms 4088 KB Output is correct
13 Correct 28 ms 3968 KB Output is correct
14 Correct 30 ms 4096 KB Output is correct
15 Correct 29 ms 3968 KB Output is correct
16 Correct 31 ms 3968 KB Output is correct
17 Correct 28 ms 3968 KB Output is correct
18 Correct 29 ms 3968 KB Output is correct
19 Correct 28 ms 3968 KB Output is correct
20 Correct 28 ms 3968 KB Output is correct
21 Correct 32 ms 4088 KB Output is correct
22 Incorrect 27 ms 3968 KB Output isn't correct
23 Halted 0 ms 0 KB -