oj.uz

Submission #53485

# Submission time Handle Problem Language Result Execution time Memory
53485 2018-06-30T05:59:31 Z 윤교준(#1420) Regions (IOI09_regions) C++11
65 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 200005;
const int MAXK = 25005;
const int MAXT = 80;

struct BIT {
	int d[MAXN];
	void upd(int x, int r) {
		for(; x < MAXN; x += rb(x))
			d[x] += r;
	}
	int get(int x) {
		int r = 0;
		for(; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

vector<int> G[MAXN];

int PreSum[MAXT+1][MAXN];
int UpSum[MAXN][MAXT+1];
int PreAns[MAXT+1][MAXT+1];

vector<int> AV[MAXK];

int A[MAXN], prt[MAXN], cnt[MAXN], di[MAXN], dri[MAXN];
int AC[MAXK], ACO[MAXK], ACRO[MAXK];

int N, K, Q, T;

void dfs(int i, int &c) {
	cnt[i] = 1; di[i] = ++c;
	for(int v : G[i]) {
		dfs(v, c);
		cnt[i] += cnt[v];
	}
}

int main() {
	scanf("%d%d%d", &N, &K, &Q);
	scanf("%d", &A[1]);
	for(int i = 2; i <= N; i++) scanf("%d%d", &prt[i], &A[i]);
	for(int i = 1; i <= N; i++) AC[A[i]]++;
	iota(ACO, ACO+K+1, 0);
	sort(ACO+1, ACO+K+1, [&](int a, int b) {
		return AC[a] > AC[b];
	});
	for(int i = 1; i <= K; i++) ACRO[ACO[i]] = i;

	T = min(N, MAXT);

	for(int i = 2; i <= N; i++) G[prt[i]].pb(i);

	{
		int c = 0;
		dfs(1, c);
	}

	for(int i = 1; i <= N; i++) dri[di[i]] = i;
	for(int i = 1; i <= N; i++) AV[A[i]].pb(i);

	for(int ai = 1, a; ai <= T; ai++) {
		a = ACO[ai];
		for(int v : AV[a]) PreSum[ai][di[v]]++;
		for(int i = 1; i <= N; i++)
			PreSum[ai][i] += PreSum[ai][i-1];
	}

	for(int ai = 1, a; ai <= T; ai++) {
		a = ACO[ai];

		for(int bi = 1, b; bi <= T; bi++) if(ai != bi) {
			b = ACO[bi];

			int &ret = PreAns[ai][bi];
			for(int v : AV[a])
				ret += PreSum[bi][di[v]+cnt[v]-1] - PreSum[bi][di[v]];
		}
	}

	if(ACRO[A[1]] <= T) UpSum[1][ACRO[A[1]]]++;
	for(int ii = 2, i; ii <= N; ii++) {
		i = dri[ii];
		for(int j = 1; j <= T; j++)
			UpSum[i][j] = UpSum[prt[i]][j];
		if(ACRO[A[i]] <= T) UpSum[i][ACRO[A[i]]]++;
	}

	for(int qi = 0; qi < Q; qi++) {
		int r0, r1;
		scanf("%d%d", &r0, &r1);

		if(ACRO[r0] <= T && ACRO[r1] <= T) {
			printf("%d\n", PreAns[ACRO[r0]][ACRO[r1]]);
			fflush(stdout);
			continue;
		}
		if(ACRO[r0] <= T) {
			int ret = 0;
			for(int v : AV[r1])
				ret += UpSum[v][ACRO[r0]];
			printf("%d\n", ret);
			fflush(stdout);
			continue;
		}
		if(ACRO[r1] <= T) {
			int ret = 0;
			for(int v : AV[r0])
				ret += PreSum[ACRO[r1]][di[v]+cnt[v]-1] - PreSum[ACRO[r1]][di[v]];
			printf("%d\n", ret);
			fflush(stdout);
			continue;
		}

		int ret = 0;
		for(int v : AV[r1]) bit.upd(di[v], 1);
		for(int v : AV[r0])
			ret += bit.get(di[v]+cnt[v]-1) - bit.get(di[v]);
		for(int v : AV[r1]) bit.upd(di[v], -1);
		printf("%d\n", ret);
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:118:19: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   for(int bi = 1, b; bi <= T; bi++) if(ai != bi) {
                   ^
regions.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:88:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 2; i <= N; i++) scanf("%d%d", &prt[i], &A[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r0, &r1);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5752 KB Output is correct
2 Correct 6 ms 5816 KB Output is correct
3 Correct 8 ms 6124 KB Output is correct
4 Correct 10 ms 6332 KB Output is correct
5 Correct 9 ms 6612 KB Output is correct
6 Correct 14 ms 7040 KB Output is correct
7 Correct 30 ms 7348 KB Output is correct
8 Correct 23 ms 7752 KB Output is correct
9 Correct 56 ms 10044 KB Output is correct
10 Correct 63 ms 13244 KB Output is correct
11 Correct 147 ms 16700 KB Output is correct
12 Correct 131 ms 20412 KB Output is correct
13 Correct 219 ms 22588 KB Output is correct
14 Correct 303 ms 27068 KB Output is correct
15 Correct 344 ms 35900 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1214 ms 58668 KB Output is correct
2 Correct 1565 ms 60712 KB Output is correct
3 Correct 2827 ms 69948 KB Output is correct
4 Correct 311 ms 69948 KB Output is correct
5 Correct 424 ms 69948 KB Output is correct
6 Correct 522 ms 69948 KB Output is correct
7 Correct 1063 ms 69948 KB Output is correct
8 Correct 1848 ms 78852 KB Output is correct
9 Correct 3422 ms 110908 KB Output is correct
10 Correct 5101 ms 128796 KB Output is correct
11 Execution timed out 8044 ms 131072 KB Time limit exceeded (wall clock)
12 Incorrect 2435 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 3257 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 3527 ms 131072 KB Unexpected end of file - int32 expected
15 Incorrect 6136 ms 131072 KB Unexpected end of file - int32 expected
16 Incorrect 6077 ms 131072 KB Unexpected end of file - int32 expected
17 Incorrect 5672 ms 131072 KB Unexpected end of file - int32 expected