Submission #428259

#	Time	Username	Problem	Language	Result	Execution time	Memory
428259		songc	Counterspells (CPSPC17_counterspells)	C++14	0 / 100	277 ms	25692 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, num=-1;
int Pa[202020], P[202020];
int W[202020], I[202020], T[202020];
int X[202020], H[202020];
vector<int> adj[202020];
set<int> B[202020];

void upd(int k){k++;while(k<=N+1)T[k]++,k+=k&-k;}
int f(int k){int r=0;k++;while(k)r+=T[k],k^=k&-k;return r;}

void dfs(int u){
	W[u] = 1;
	for (int v : adj[u]) dfs(v), W[u] += W[v];
	sort(adj[u].begin(), adj[u].end(), [&](int a, int b){return W[a] > W[b];});
}

void hld(int u, int h){
	I[u] = ++num, P[I[u]] = I[Pa[u]], H[I[u]] = I[h];
	if (!adj[u].size()) return;
	hld(adj[u][0], h);
	for (int v : adj[u]){
		if (v == adj[u][0]) continue;
		hld(v, v);
	}
}

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%d", &Pa[i]), adj[Pa[i]].pb(i);
	dfs(0), hld(0, 0);
	for (int i=1; i<=N; i++){
		int u = I[i];
		int ans = 0;
		vector<int> up;
		upd(u), upd(u+1);
		while (u>=0){
			auto it = B[H[u]].lb(u);
			if (it != B[H[u]].begin()){
				int v = *(--it);
				ans += u-v;
				upd(v+1), upd(u+1);
				break;
			}
			int v = H[u];
			ans += u-v+1;
			if (!(f(v)&1) && v) X[P[v]]--;
			upd(v), upd(u+1);
			if (!v || X[P[v]] || (H[P[v]] == H[P[v]+1] && !(f(P[v]+1)&1))) u = -1;
			else u = P[v];
			if (!(f(v)&1) && v) X[P[v]]++;
			up.pb(P[v]);
		}
		for (int v : up){
			if (X[v]) B[H[v]].insert(v);
			else B[H[v]].erase(v);
		}
		printf("%d\n", ans-1);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  for (int i=1; i<=N; i++) scanf("%d", &Pa[i]), adj[Pa[i]].pb(i);
      |                           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20