oj.uz

Submission #211143

# Submission time Handle Problem Language Result Execution time Memory
211143 2020-03-19T10:11:32 Z nvmdava Construction of Highway (JOI18_construction) C++17
0 / 100
 6 ms 2816 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f

vector<int> ch[N];

int le[N], c[N], ri[N], p[N][17], d[N];
int cntr = 0;
int bit[N], seg[N * 3];

void updateseg(int id, int l, int r, int x, int v){
	if(l > x || r < x) return;
	seg[id] = max(seg[id], v);
	if(l == r) return;
	int m = (l + r) >> 1;
	updateseg(id << 1, l, m, x, v);
	updateseg(id << 1 | 1, m + 1, r, x, v);
}

int queryseg(int id, int l, int r, int L, int R){
	if(L <= l && r <= R) return seg[id];
	if(l > R || r < L) return 0;
	int m = (l + r) >> 1;
	return max(queryseg(id << 1, l, m, L, R), queryseg(id << 1 | 1, m + 1, r, L, R));
}

void updatebit(int x, int v){
	while(x < N){
		bit[x] += v;
		x += x & -x;
	}
}
int querybit(int x){
	int s = 0;
	while(x){
		s += bit[x];
		x -= x & -x;
	}
	return s;
}

void dfs(int v = 1){
	le[v] = ++cntr;
	for(int i = 0; i < 16; ++i)
		p[v][i + 1] = p[p[v][i]][i];

	for(int x : ch[v]){
		p[x][0] = v;
		d[x] = d[v] + 1;
		dfs(x);
	}
	ri[v] = cntr;
}

map<int, int> cmp;

vector<pair<int, int > > mark;

int ord[N];

int lca(int v, int u){
	for(int i = 16; i >= 0; --i)
		if(le[p[v][i]] > le[u] || ri[u] > ri[p[v][i]])
			v = p[v][i];
	return v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i){
    	cin>>c[i];
    	cmp[c[i]] = 0;
    }
    ri[0] = n;

    for(auto& x : cmp)
	    x.ss = ++cntr;
    for(int i = 1; i <= n; ++i)
    	c[i] = n + 1 - cmp[c[i]];

    for(int i = 2; i <= n; ++i){
    	int v;
    	cin>>v>>ord[i];
    	ch[v].push_back(ord[i]);
    }
    cntr = 0;
    updateseg(1, 1, n, 1, 1);
    ord[1] = 1;
    dfs();
    for(int i = 2; i <= n; ++i){
    	int v = 1;
    	ll ans = 0;
    	while(v != ord[i]){
    		int u = ord[queryseg(1, 1, n, le[v], ri[v])];
    		int val = c[u];
    		u = lca(ord[i], u);
    		ans += querybit(val - 1);
    		updatebit(val, d[u] - d[v]);
    		mark.push_back({val, d[u] - d[v]});
    		v = u;
    	}
    	updateseg(1, 1, n, le[ord[i]], i);
    	while(!mark.empty()){
    		updatebit(mark.back().ff, -mark.back().ss);
    		mark.pop_back();
    	}
    	cout<<ans<<'\n';
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Incorrect 6 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Incorrect 6 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Incorrect 6 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -