oj.uz

Submission #53492

# Submission time Handle Problem Language Result Execution time Memory
53492 2018-06-30T06:16:08 Z 윤교준(#1420) Regions (IOI09_regions) C++11
65 / 100
 7534 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 = 200000;
const int MAXK = 25000;
const int MAXT = 160;

struct BIT {
	int d[MAXN+1];
	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+1];

int PreDI[MAXN+1];
int PreDIS[MAXT+1], PreDIE[MAXT+1];

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

vector<int> AV[MAXK+1];

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

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(K, 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];
		PreDIS[ai] = PreDIE[ai-1];
		int &i = PreDIE[ai]; i = PreDIS[ai];
		for(int v : AV[a]) PreDI[i++] = di[v];
		sort(PreDI + PreDIS[ai], PreDI + i);

/*
		printf("ai=%d, a=%d, s=%d, e=%d\n", ai, a, PreDIS[ai], i);
		for(int j = PreDIS[ai]; j < i; j++)
			printf("%d ", PreDI[j]);
		puts("");
*/
	}

	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 += (int)(upper_bound(PreDI+PreDIS[bi], PreDI+PreDIE[bi], di[v]+cnt[v]-1)
							- upper_bound(PreDI+PreDIS[bi], PreDI+PreDIE[bi], di[v]));

			//printf("a=%d, b=%d, ret=%d\n", a, b, ret);
		}
	}

	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 += (int)(upper_bound(PreDI+PreDIS[ACRO[r1]], PreDI+PreDIE[ACRO[r1]], di[v]+cnt[v]-1)
							- upper_bound(PreDI+PreDIS[ACRO[r1]], PreDI+PreDIE[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:128: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:88: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:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:90: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:150: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 5624 KB Output is correct
2 Correct 6 ms 5688 KB Output is correct
3 Correct 8 ms 5852 KB Output is correct
4 Correct 10 ms 5852 KB Output is correct
5 Correct 11 ms 6296 KB Output is correct
6 Correct 28 ms 6540 KB Output is correct
7 Correct 32 ms 6904 KB Output is correct
8 Correct 45 ms 7304 KB Output is correct
9 Correct 43 ms 9608 KB Output is correct
10 Correct 82 ms 12828 KB Output is correct
11 Correct 213 ms 16392 KB Output is correct
12 Correct 230 ms 19980 KB Output is correct
13 Correct 311 ms 22324 KB Output is correct
14 Correct 549 ms 26628 KB Output is correct
15 Correct 378 ms 35648 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1765 ms 58620 KB Output is correct
2 Correct 1721 ms 60784 KB Output is correct
3 Correct 3375 ms 70056 KB Output is correct
4 Correct 413 ms 70056 KB Output is correct
5 Correct 535 ms 70056 KB Output is correct
6 Correct 909 ms 70056 KB Output is correct
7 Correct 1098 ms 70056 KB Output is correct
8 Correct 2058 ms 78796 KB Output is correct
9 Correct 3409 ms 110908 KB Output is correct
10 Correct 5633 ms 128544 KB Output is correct
11 Execution timed out 7534 ms 131072 KB Time limit exceeded (wall clock)
12 Incorrect 3449 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 4791 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 4843 ms 131072 KB Unexpected end of file - int32 expected
15 Execution timed out 6564 ms 131072 KB Time limit exceeded (wall clock)
16 Incorrect 5687 ms 131072 KB Unexpected end of file - int32 expected
17 Incorrect 5390 ms 131072 KB Unexpected end of file - int32 expected