oj.uz

Submission #722460

# Submission time Handle Problem Language Result Execution time Memory
722460 2023-04-12T03:05:16 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 14396 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 14416 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 14356 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 14416 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 14416 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 14416 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 14416 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 14544 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 14800 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 14928 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 15312 KB Time limit exceeded (wall clock)
12 Execution timed out 13 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 20 ms 18100 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 185 ms 20040 KB Time limit exceeded (wall clock)
2 Execution timed out 228 ms 18884 KB Time limit exceeded (wall clock)
3 Execution timed out 166 ms 21908 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 16116 KB Time limit exceeded (wall clock)
5 Execution timed out 16 ms 17360 KB Time limit exceeded (wall clock)
6 Runtime error 666 ms 68188 KB Execution killed with signal 11
7 Runtime error 1078 ms 82328 KB Execution killed with signal 11
8 Runtime error 848 ms 92636 KB Execution killed with signal 11
9 Execution timed out 59 ms 24136 KB Time limit exceeded (wall clock)
10 Runtime error 1919 ms 131072 KB Execution killed with signal 11
11 Execution timed out 81 ms 24344 KB Time limit exceeded (wall clock)
12 Execution timed out 8007 ms 55888 KB Time limit exceeded
13 Runtime error 5563 ms 121000 KB Execution killed with signal 11
14 Runtime error 7018 ms 131072 KB Execution killed with signal 11
15 Runtime error 3609 ms 131072 KB Execution killed with signal 11
16 Runtime error 2264 ms 131072 KB Execution killed with signal 11
17 Runtime error 2116 ms 131072 KB Execution killed with signal 11