oj.uz

Submission #1094369

# Submission time Handle Problem Language Result Execution time Memory
1094369 2024-09-29T13:11:47 Z Sunbae September (APIO24_september) C++17
0 / 100
 3 ms 5980 KB 
#include <bits/stdc++.h>
#include "september.h"
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
vector<int> g[N];
int vis[N], tin[N], tout[N], T[N], mn[N], mx[N], bit[M], ti, MX, MN;
void upd(int i, int v){ for(; i<M; i+=i&-i) bit[i] += v;}
int qry(int i){ int r = 0; for(; i; i-=i&-i) r += bit[i]; return r;}
void dfs(int u){
	tin[u] = ti++; T[tin[u]] = u;
	for(int v: g[u]) dfs(v);
	tout[u] = ti-1;
}
int solve(int n, int m, vector<int> up, vector<vector<int>> S){
	for(int i = 0; i<n; ++i) g[i].clear();
	for(int i = ti = 1; i<n; ++i) g[up[i]].push_back(i);
	dfs(0);
	fill(mx, mx+n, MX = INT_MIN); fill(mn, mn+n, MN = INT_MAX);
	for(int i = 0, cnt = 1; i<m; ++i){
		fill(vis, vis+n, 0);
		for(int u: S[i]){
			if(!vis[u]){
				for(int j = tin[u]; j<=tout[u]; ++j) vis[T[tin[u]]] = cnt;
				++cnt;
			}	
		}
		for(int i = 1; i<n; ++i){
			mx[i] = max(mx[i], vis[i]); 
			mn[i] = min(mn[i], vis[i]);
		}
	}
	fill(bit, bit+M, 0);
	for(int i = 1; i<n; ++i){
		int l = mn[i] * 2, r = mx[i] * 2;
		upd(l, +1); upd(r+1, -1);
		MN = min(MN, l); MX = max(MX, r);
	}
	int ans = 0;
	for(int i = MN; i<=MX; ++i) if(!qry(i-1) && qry(i)) ++ans;
	return ans;
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 14.0

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

Subtask #3
0.0 / 5.0

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

Subtask #4
0.0 / 9.0

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

Subtask #5
0.0 / 5.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 9.0

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

Subtask #8
0.0 / 11.0

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

Subtask #9
0.0 / 9.0

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

Subtask #10
0.0 / 16.0

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