oj.uz

Submission #53499

# Submission time Handle Problem Language Result Execution time Memory
53499 2018-06-30T06:29:26 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 = 200000;
const int MAXK = 25000;
const int MAXT = 140;

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 8 ms 5812 KB Output is correct
3 Correct 8 ms 5812 KB Output is correct
4 Correct 10 ms 5812 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 38 ms 6384 KB Output is correct
7 Correct 45 ms 6768 KB Output is correct
8 Correct 61 ms 7152 KB Output is correct
9 Correct 54 ms 9200 KB Output is correct
10 Correct 75 ms 12004 KB Output is correct
11 Correct 202 ms 15216 KB Output is correct
12 Correct 211 ms 18556 KB Output is correct
13 Correct 271 ms 20412 KB Output is correct
14 Correct 522 ms 24380 KB Output is correct
15 Correct 357 ms 32584 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1884 ms 52692 KB Output is correct
2 Correct 1950 ms 54500 KB Output is correct
3 Correct 3965 ms 63032 KB Output is correct
4 Correct 483 ms 63032 KB Output is correct
5 Correct 443 ms 63032 KB Output is correct
6 Correct 916 ms 63032 KB Output is correct
7 Correct 1203 ms 63032 KB Output is correct
8 Correct 1806 ms 70868 KB Output is correct
9 Correct 3259 ms 99084 KB Output is correct
10 Correct 5572 ms 115200 KB Output is correct
11 Execution timed out 8023 ms 126868 KB Time limit exceeded (wall clock)
12 Incorrect 2891 ms 126868 KB Unexpected end of file - int32 expected
13 Incorrect 3571 ms 126868 KB Unexpected end of file - int32 expected
14 Incorrect 4032 ms 128540 KB Unexpected end of file - int32 expected
15 Incorrect 5353 ms 131072 KB Unexpected end of file - int32 expected
16 Incorrect 6241 ms 131072 KB Unexpected end of file - int32 expected
17 Incorrect 5793 ms 131072 KB Unexpected end of file - int32 expected