oj.uz

Submission #428249

# Submission time Handle Problem Language Result Execution time Memory
428249 2021-06-15T09:05:15 Z songc Counterspells (CPSPC17_counterspells) C++14
0 / 100
 328 ms 23648 KB 
#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;
		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]);
		}
		upd(I[i]), upd(I[i]+1);
		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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 23648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -