Submission #219770

#	Time	Username	Problem	Language	Result	Execution time	Memory
219770		patrikpavic2	Construction of Highway (JOI18_construction)	C++17	100 / 100	826 ms	24176 KiB

construction

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 1e5 + 500;
const int LOG = 17;
const int OFF = (1 << LOG);

ll inv, ans[N];
vector < int > saz, v[N];
int loga[N], siz = 0, koga[N], C[N], n, cur;
int A[N], B[N], L[N], R[N];
int vrh[N], dep[N], dno[N], par[N][LOG], lan[N];

void add(int x, int y){
	siz += y;
	for(; x < N ; x += x & -x)
		loga[x] += y;
}

int query(int x){
	int ret = 0;
	for(; x ; x -= x & -x)
		ret += loga[x];
	return ret;
}


void dfs(int x,int lst){
	par[x][0] = lst; dep[x] = dep[lst] + 1;
	L[x] = cur++;
	for(int y : v[x])
		dfs(y, x);
	R[x] = cur - 1;
}

void precompute(){
	for(int j = 1;j < LOG;j++)
		for(int i = 1;i <= n;i++)
			par[i][j] = par[par[i][j - 1]][j - 1];
}

int digni(int x,int k){
	for(int i = LOG - 1;i >= 0;i--)
		if(k & (1 << i)) x = par[x][i];
	return x;
}

int tour[2 * OFF];

void update(int i,int x){
	tour[i + OFF] = x;
	for(i = (i + OFF) / 2; i ; i /= 2)
		tour[i] = max(tour[2 * i], tour[2 * i + 1]);
}

int query(int i,int a,int b,int lo,int hi){
	if(lo <= a && b <= hi) return tour[i];
	if(a > hi || b < lo) return 0;
	return max(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int gdje(int i){
	return query(1, 0, OFF - 1, L[i], R[i]);
}

ll odradi(int st){
	int x = gdje(st);
	ll inv = 0;
	vector < pii > brisi;
	for(;;){
		inv += (ll)query(C[dno[x]] - 1) * (dep[st] - dep[vrh[x]] + 1);
		add(C[dno[x]], dep[st] - dep[vrh[x]] + 1);
		brisi.PB({C[dno[x]], dep[st] - dep[vrh[x]] + 1});
		int ol_vrh = vrh[x];
		if(st != dno[x]){
			vrh[x] = digni(dno[x], dep[dno[x]] - dep[st] - 1);
		}
		if(!(ol_vrh - 1)) break;
		st = par[ol_vrh][0];
		x = gdje(st);
	}
	for(pii tmp : brisi)
		add(tmp.X, -tmp.Y);
	return inv;
}

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		scanf("%d", C + i), saz.PB(C[i]);
	}
	sort(saz.begin(), saz.end());
	for(int i = 1;i <= n;i++)
		C[i] = lower_bound(saz.begin(), saz.end(), C[i]) - saz.begin() + 1;
	for(int i = 1;i < n;i++){
		scanf("%d%d", A + i, B + i);
		v[A[i]].PB(B[i]);
	}
	dfs(1, 1); precompute();
	vrh[0] = 1, dno[0] = 1;
	for(int i = 1;i < n;i++){
		printf("%lld\n", odradi(A[i]));
		dno[i] = B[i], vrh[i] = 1;
		update(L[B[i]], i);
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
construction.cpp:100:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i), saz.PB(C[i]);
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
construction.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84