oj.uz

Submission #53518

# Submission time Handle Problem Language Result Execution time Memory
53518 2018-06-30T06:54:25 Z 윤교준(#1420) Regions (IOI09_regions) C++11
65 / 100
 7824 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;

unordered_map<int, int> MP;

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);

		int key = r0*(MAXK+1) + r1;
		{
			auto it = MP.find(key);
			if(MP.end() != it) {
				printf("%d\n", it -> second);
				fflush(stdout);
				continue;
			}
		}

		if(ACRO[r0] <= T && ACRO[r1] <= T) {
			printf("%d\n", MP[key] = 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", MP[key] = 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", MP[key] = 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", MP[key] = ret);
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:130: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:90: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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:92: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:152: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 7 ms 5628 KB Output is correct
2 Correct 7 ms 5688 KB Output is correct
3 Correct 8 ms 5764 KB Output is correct
4 Correct 11 ms 5936 KB Output is correct
5 Correct 16 ms 6268 KB Output is correct
6 Correct 28 ms 6684 KB Output is correct
7 Correct 32 ms 7108 KB Output is correct
8 Correct 51 ms 7584 KB Output is correct
9 Correct 86 ms 9888 KB Output is correct
10 Correct 125 ms 13216 KB Output is correct
11 Correct 240 ms 16768 KB Output is correct
12 Correct 240 ms 20596 KB Output is correct
13 Correct 338 ms 23024 KB Output is correct
14 Correct 557 ms 27188 KB Output is correct
15 Correct 510 ms 36264 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1644 ms 60016 KB Output is correct
2 Correct 1624 ms 62104 KB Output is correct
3 Correct 2478 ms 72976 KB Output is correct
4 Correct 391 ms 72976 KB Output is correct
5 Correct 520 ms 72976 KB Output is correct
6 Correct 714 ms 72976 KB Output is correct
7 Correct 1048 ms 72976 KB Output is correct
8 Correct 1622 ms 81744 KB Output is correct
9 Correct 3530 ms 116672 KB Output is correct
10 Correct 5183 ms 131072 KB Output is correct
11 Execution timed out 7824 ms 131072 KB Time limit exceeded (wall clock)
12 Incorrect 3377 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 4463 ms 131072 KB Unexpected end of file - int32 expected
14 Execution timed out 6017 ms 131072 KB Time limit exceeded (wall clock)
15 Execution timed out 5679 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 5450 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 6132 ms 131072 KB Time limit exceeded (wall clock)