oj.uz

Submission #722465

# Submission time Handle Problem Language Result Execution time Memory
722465 2023-04-12T03:28:54 Z ono_de206 Regions (IOI09_regions) C++14
0 / 100
 8000 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, B = 400;
int cnt[510][25010], in[mxn], out[mxn], tt, kk[mxn], s[mxn], h[mxn];
vector<int> g[mxn], p[25010], d[25010];

void dfs(int to) {
	in[to] = ++tt;
	d[h[to]].pb(in[to]);
	for(int x : g[to]) {
		dfs(x);
	}
	out[to] = tt;
}

void solve(int to, int cn, int id) {
	cnt[kk[id]][h[to]] += cn;
	cn += (h[to] == id);
	for(int x : g[to]) {
		solve(x, cn, id);
	}
	cn -= (h[to] == id);
}

void go() {
	int n, r, q;
	cin >> n >> r >> q;
	for(int i = 1; i<= n; i++) {
		if(i == 1)
			cin >> h[i];
		else
			cin >> s[i] >> h[i];
		p[h[i]].pb(i);
		if(i > 1) g[s[i]].pb(i);
	}
	dfs(1);
	tt = 0;
	for(int i = 1; i <= r; i++) {
		if(p[h[i]].size() >= B) {
			kk[i] = ++tt;
			solve(1, 0, i);
		}
		sort(all(d[i]));
	}
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if(p[r1].size() >= B) {
			cout << cnt[kk[r1]][r2] << '\n';
		}
		else {
			int ans = 0;
			for(int x : p[r1]) {
				int ll = lower_bound(all(d[r2]), in[x]) - d[r2].begin();
				int rr = upper_bound(all(d[r2]), out[x]) - d[r2].begin();
				ans += rr - ll;
			}
			cout << ans << '\n';
		}
	}
}
 
signed main() {
	// #ifndef
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6608 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 6692 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 6992 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 7552 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 7268 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 7852 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 9808 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 176 ms 11632 KB Time limit exceeded (wall clock)
2 Execution timed out 261 ms 10492 KB Time limit exceeded (wall clock)
3 Execution timed out 163 ms 13480 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 7888 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 9168 KB Time limit exceeded (wall clock)
6 Runtime error 707 ms 51252 KB Execution killed with signal 11
7 Runtime error 1111 ms 65676 KB Execution killed with signal 11
8 Runtime error 834 ms 75992 KB Execution killed with signal 11
9 Execution timed out 54 ms 15936 KB Time limit exceeded (wall clock)
10 Runtime error 1812 ms 131072 KB Execution killed with signal 11
11 Execution timed out 85 ms 16180 KB Time limit exceeded (wall clock)
12 Execution timed out 8007 ms 51072 KB Time limit exceeded
13 Runtime error 5767 ms 104988 KB Execution killed with signal 11
14 Runtime error 7448 ms 120732 KB Execution killed with signal 11
15 Runtime error 3795 ms 131072 KB Execution killed with signal 11
16 Runtime error 2314 ms 131072 KB Execution killed with signal 11
17 Runtime error 2150 ms 131072 KB Execution killed with signal 11