oj.uz

Submission #996572

# Submission time Handle Problem Language Result Execution time Memory
996572 2024-06-10T20:03:28 Z Shayan86 September (APIO24_september) C++17
100 / 100
 555 ms 23828 KB 
#include "september.h"

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

//! segment
#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 50;
const ll inf = 1e9 + 7;

int n, m, st[N], ft[N], timer;

vector<int> adj[N];

void dfs(int v){
	st[v] = timer++;
	for(int u: adj[v]) dfs(u);
	ft[v] = timer;
}

int seg[N*4], lz[N*4];

void quex(int id, int x){
    seg[id] += x;
    lz[id] += x;
}

void relax(int id){
    quex(lid, lz[id]);
    quex(rid, lz[id]);
    lz[id] = 0;
}

int get(int s, int t, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= t) return seg[id];
    if(t <= l || r <= s) return 0;

    relax(id);
    return max(get(s, t, l, mid, lid), get(s, t, mid, r, rid));
}

void upd(int s, int t, int x, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= t){
        quex(id, x); return;
    }
	if(t <= l || r <= s) return;

    relax(id);
	upd(s, t, x, l, mid, lid);
	upd(s, t, x, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

set<int> ms;

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n = N; m = M;

	ms.clear(); timer = 0;
	fill(seg, seg + (n+20) * 4, 0);
	fill(lz, lz + (n+20) * 4, 0);
	for(int i = 0; i < n; i++) adj[i].clear();

	for(int i = 1; i < n; i++) adj[F[i]].pb(i);
	dfs(0);

	int res = 0;
	for(int i = 0; i < n-1; i++){
		for(int j = 0; j < m; j++) ms.insert(S[j][i]);
		upd(st[S[0][i]], ft[S[0][i]], 1);
		upd(st[S[0][i]], st[S[0][i]]+1, -inf);

		if(SZ(ms) == i+1 && get(0, n) <= 0) res++;
	}

	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5720 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5724 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5788 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 5720 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5788 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 2 ms 5724 KB Output is correct
13 Correct 2 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 2 ms 5724 KB Output is correct
16 Correct 2 ms 5724 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5788 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5720 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5724 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct
15 Correct 2 ms 5720 KB Output is correct
16 Correct 2 ms 5724 KB Output is correct
17 Correct 2 ms 5788 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 5724 KB Output is correct
20 Correct 2 ms 5724 KB Output is correct
21 Correct 2 ms 5724 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 2 ms 5724 KB Output is correct
24 Correct 2 ms 5724 KB Output is correct
25 Correct 2 ms 5720 KB Output is correct
26 Correct 3 ms 5720 KB Output is correct
27 Correct 2 ms 5724 KB Output is correct
28 Correct 3 ms 5724 KB Output is correct
29 Correct 2 ms 5724 KB Output is correct
30 Correct 2 ms 5724 KB Output is correct
31 Correct 2 ms 5724 KB Output is correct
32 Correct 2 ms 5724 KB Output is correct
33 Correct 3 ms 5724 KB Output is correct
34 Correct 2 ms 5724 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5788 KB Output is correct
4 Correct 336 ms 21864 KB Output is correct
5 Correct 348 ms 21932 KB Output is correct
6 Correct 368 ms 21920 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 5720 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5788 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 2 ms 5724 KB Output is correct
13 Correct 2 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 2 ms 5724 KB Output is correct
16 Correct 2 ms 5724 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Correct 336 ms 21864 KB Output is correct
19 Correct 348 ms 21932 KB Output is correct
20 Correct 368 ms 21920 KB Output is correct
21 Correct 555 ms 19136 KB Output is correct
22 Correct 552 ms 18092 KB Output is correct
23 Correct 555 ms 20104 KB Output is correct
24 Correct 541 ms 20048 KB Output is correct
25 Correct 537 ms 19404 KB Output is correct
26 Correct 543 ms 19112 KB Output is correct
27 Correct 539 ms 17324 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5788 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 336 ms 21864 KB Output is correct
8 Correct 348 ms 21932 KB Output is correct
9 Correct 368 ms 21920 KB Output is correct
10 Correct 131 ms 22436 KB Output is correct
11 Correct 131 ms 22732 KB Output is correct
12 Correct 129 ms 23828 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 1 ms 5724 KB Output is correct
11 Correct 1 ms 5720 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5724 KB Output is correct
14 Correct 1 ms 5724 KB Output is correct
15 Correct 2 ms 5720 KB Output is correct
16 Correct 2 ms 5724 KB Output is correct
17 Correct 2 ms 5788 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 5724 KB Output is correct
20 Correct 2 ms 5724 KB Output is correct
21 Correct 2 ms 5724 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 2 ms 5724 KB Output is correct
24 Correct 2 ms 5724 KB Output is correct
25 Correct 2 ms 5720 KB Output is correct
26 Correct 3 ms 5720 KB Output is correct
27 Correct 2 ms 5724 KB Output is correct
28 Correct 3 ms 5724 KB Output is correct
29 Correct 2 ms 5724 KB Output is correct
30 Correct 2 ms 5724 KB Output is correct
31 Correct 2 ms 5724 KB Output is correct
32 Correct 2 ms 5724 KB Output is correct
33 Correct 3 ms 5724 KB Output is correct
34 Correct 2 ms 5724 KB Output is correct
35 Correct 336 ms 21864 KB Output is correct
36 Correct 348 ms 21932 KB Output is correct
37 Correct 368 ms 21920 KB Output is correct
38 Correct 555 ms 19136 KB Output is correct
39 Correct 552 ms 18092 KB Output is correct
40 Correct 555 ms 20104 KB Output is correct
41 Correct 541 ms 20048 KB Output is correct
42 Correct 537 ms 19404 KB Output is correct
43 Correct 543 ms 19112 KB Output is correct
44 Correct 539 ms 17324 KB Output is correct
45 Correct 131 ms 22436 KB Output is correct
46 Correct 131 ms 22732 KB Output is correct
47 Correct 129 ms 23828 KB Output is correct
48 Correct 181 ms 19400 KB Output is correct
49 Correct 186 ms 19400 KB Output is correct
50 Correct 176 ms 19404 KB Output is correct
51 Correct 176 ms 20168 KB Output is correct
52 Correct 179 ms 19352 KB Output is correct
53 Correct 182 ms 19400 KB Output is correct
54 Correct 171 ms 20172 KB Output is correct