oj.uz

Submission #246357

# Submission time Handle Problem Language Result Execution time Memory
246357 2020-07-08T20:54:35 Z fivefourthreeone Construction of Highway (JOI18_construction) C++17
0 / 100
 9 ms 3712 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 prev = a;
        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";
        }
        for(int k: path) {
            del(k);
        }
        cout<<ans<<"\n";
        upd(inout[b].first, i);
        //cout<<inout[b].first<<" "<<i<<" cool\n";
    }
    return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:118:13: warning: unused variable 'prev' [-Wunused-variable]
         int prev = a;
             ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3712 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct
9 Correct 7 ms 3712 KB Output is correct
10 Correct 7 ms 3712 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 7 ms 3584 KB Output is correct
13 Correct 9 ms 3584 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 9 ms 3712 KB Output is correct
16 Correct 8 ms 3584 KB Output is correct
17 Correct 8 ms 3712 KB Output is correct
18 Correct 7 ms 3584 KB Output is correct
19 Correct 7 ms 3584 KB Output is correct
20 Correct 9 ms 3584 KB Output is correct
21 Correct 8 ms 3584 KB Output is correct
22 Incorrect 7 ms 3584 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3712 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct
9 Correct 7 ms 3712 KB Output is correct
10 Correct 7 ms 3712 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 7 ms 3584 KB Output is correct
13 Correct 9 ms 3584 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 9 ms 3712 KB Output is correct
16 Correct 8 ms 3584 KB Output is correct
17 Correct 8 ms 3712 KB Output is correct
18 Correct 7 ms 3584 KB Output is correct
19 Correct 7 ms 3584 KB Output is correct
20 Correct 9 ms 3584 KB Output is correct
21 Correct 8 ms 3584 KB Output is correct
22 Incorrect 7 ms 3584 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3712 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct
9 Correct 7 ms 3712 KB Output is correct
10 Correct 7 ms 3712 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 7 ms 3584 KB Output is correct
13 Correct 9 ms 3584 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 9 ms 3712 KB Output is correct
16 Correct 8 ms 3584 KB Output is correct
17 Correct 8 ms 3712 KB Output is correct
18 Correct 7 ms 3584 KB Output is correct
19 Correct 7 ms 3584 KB Output is correct
20 Correct 9 ms 3584 KB Output is correct
21 Correct 8 ms 3584 KB Output is correct
22 Incorrect 7 ms 3584 KB Output isn't correct
23 Halted 0 ms 0 KB -