oj.uz

Submission #397832

# Submission time Handle Problem Language Result Execution time Memory
397832 2021-05-03T08:29:22 Z sinamhdv Regions (IOI09_regions) C++11
100 / 100
 4352 ms 87460 KB 
// IOI09_regions
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define MAXN 200100
#define SQRT 120
#define BLK (MAXN / SQRT + 10)

int n, rc, q;
int a[MAXN];
vector<int> col[MAXN];
int par[MAXN];
int precnt[BLK][MAXN];
vector<int> cld[MAXN];
vector<int> big;
int sttime[MAXN], fntime[MAXN], timer;
int cnt[MAXN];
int colcnt[MAXN];

void dfs(int v)
{
	FOR(i, 0, (int)big.size()) if (big[i] != a[v]) precnt[i][a[v]] += cnt[big[i]];
	col[a[v]].pb(v);
	sttime[v] = timer++;
	for (int u : cld[v])
	{
		cnt[a[v]]++;
		dfs(u);
		cnt[a[v]]--;
	}
	fntime[v] = timer;
}

bool cmp(int x, int y)
{
	return sttime[x] < sttime[y];
}

int32_t main(void)
{
	fast_io;
	cin >> n >> rc >> q;
	cin >> a[1];
	colcnt[a[1]]++;
	FOR(i, 2, n + 1)
	{
		cin >> par[i] >> a[i];
		colcnt[a[i]]++;
		cld[par[i]].pb(i);
	}

	FOR(i, 1, rc + 1)
		if (colcnt[i] > SQRT)
			big.pb(i);

	dfs(1);
	
	dbgr(big.begin(), big.end());
	dbgr(sttime + 1, sttime + n + 1);
	dbgr(fntime + 1, fntime + n + 1);
	
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		if (colcnt[x] > SQRT)
		{
			x = lower_bound(all(big), x) - big.begin();
			cout << precnt[x][y] << endl;
			continue;
		}
		int ans = 0;
		for (int u : col[x])
		{
			sttime[MAXN - 1] = fntime[u] - 1;
			ans += upper_bound(all(col[y]), MAXN - 1, cmp) - lower_bound(all(col[y]), u, cmp);
		}
		cout << ans << endl;
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 8 ms 9672 KB Output is correct
5 Correct 14 ms 9672 KB Output is correct
6 Correct 31 ms 9800 KB Output is correct
7 Correct 43 ms 9800 KB Output is correct
8 Correct 41 ms 9800 KB Output is correct
9 Correct 57 ms 10240 KB Output is correct
10 Correct 78 ms 10184 KB Output is correct
11 Correct 153 ms 10568 KB Output is correct
12 Correct 162 ms 11080 KB Output is correct
13 Correct 216 ms 10696 KB Output is correct
14 Correct 199 ms 12488 KB Output is correct
15 Correct 129 ms 15968 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 15776 KB Output is correct
2 Correct 655 ms 14204 KB Output is correct
3 Correct 1590 ms 18356 KB Output is correct
4 Correct 253 ms 13468 KB Output is correct
5 Correct 493 ms 13256 KB Output is correct
6 Correct 616 ms 14576 KB Output is correct
7 Correct 1036 ms 17592 KB Output is correct
8 Correct 1223 ms 23876 KB Output is correct
9 Correct 3078 ms 57356 KB Output is correct
10 Correct 3144 ms 86796 KB Output is correct
11 Correct 4352 ms 80392 KB Output is correct
12 Correct 2644 ms 61056 KB Output is correct
13 Correct 2927 ms 61504 KB Output is correct
14 Correct 3005 ms 63952 KB Output is correct
15 Correct 3883 ms 87460 KB Output is correct
16 Correct 3953 ms 84392 KB Output is correct
17 Correct 4210 ms 74828 KB Output is correct