oj.uz

Submission #722463

# Submission time Handle Problem Language Result Execution time Memory
722463 2023-04-12T03:22:53 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[500][mxn], in[mxn], out[mxn], tt, kk[mxn], s[mxn], h[mxn];
vector<int> g[mxn], p[mxn], d[mxn];
 
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 7 ms 14416 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 14416 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 14416 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 14416 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 14416 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 14436 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 14416 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 14544 KB Time limit exceeded (wall clock)
9 Execution timed out 11 ms 14800 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 15056 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 15312 KB Time limit exceeded (wall clock)
12 Execution timed out 12 ms 15696 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 15440 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 16080 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 18016 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 172 ms 20012 KB Time limit exceeded (wall clock)
2 Execution timed out 197 ms 18836 KB Time limit exceeded (wall clock)
3 Execution timed out 160 ms 21952 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 16208 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 17360 KB Time limit exceeded (wall clock)
6 Runtime error 655 ms 68108 KB Execution killed with signal 11
7 Runtime error 1085 ms 82492 KB Execution killed with signal 11
8 Runtime error 842 ms 92836 KB Execution killed with signal 11
9 Execution timed out 60 ms 24040 KB Time limit exceeded (wall clock)
10 Runtime error 1761 ms 131072 KB Execution killed with signal 11
11 Execution timed out 76 ms 24492 KB Time limit exceeded (wall clock)
12 Execution timed out 8096 ms 57960 KB Time limit exceeded
13 Runtime error 5894 ms 120960 KB Execution killed with signal 11
14 Runtime error 7454 ms 131072 KB Execution killed with signal 11
15 Runtime error 3706 ms 131072 KB Execution killed with signal 11
16 Runtime error 2302 ms 131072 KB Execution killed with signal 11
17 Runtime error 2212 ms 131072 KB Execution killed with signal 11