oj.uz

Submission #53494

# Submission time Handle Problem Language Result Execution time Memory
53494 2018-06-30T06:25:07 Z 윤교준(#1420) Regions (IOI09_regions) C++11
44 / 100
 7963 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("");
*/
	}

	if(K <= 300) {
		int PreAnsTT[301][301];

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

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

				int &ret = PreAnsTT[ai][bi];
				ret = 0;
				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]));
			}
		}

		for(int qi = 0; qi < Q; qi++) {
			int r0, r1; scanf("%d%d", &r0, &r1);
			printf("%d\n", PreAnsTT[ACRO[r0]][ACRO[r1]]);
			fflush(stdout);
		}

		return 0;
	}

	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:131:20: warning: variable 'b' set but not used [-Wunused-but-set-variable]
    for(int bi = 1, b; bi <= K; bi++) if(ai != bi) {
                    ^
regions.cpp:154: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:143:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int r0, r1; scanf("%d%d", &r0, &r1);
                ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:176: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
9.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 9 ms 5684 KB Output is correct
3 Correct 10 ms 5892 KB Output is correct
4 Correct 10 ms 5892 KB Output is correct
5 Correct 13 ms 5892 KB Output is correct
6 Incorrect 26 ms 6144 KB Output isn't correct
7 Correct 37 ms 6144 KB Output is correct
8 Incorrect 47 ms 6168 KB Output isn't correct
9 Incorrect 83 ms 6712 KB Output isn't correct
10 Correct 87 ms 13072 KB Output is correct
11 Incorrect 308 ms 13072 KB Output isn't correct
12 Correct 254 ms 20084 KB Output is correct
13 Correct 350 ms 22304 KB Output is correct
14 Incorrect 582 ms 22304 KB Output isn't correct
15 Incorrect 579 ms 22304 KB Output isn't correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2016 ms 22304 KB Output isn't correct
2 Incorrect 2479 ms 22304 KB Output isn't correct
3 Incorrect 3737 ms 22304 KB Output isn't correct
4 Correct 560 ms 26816 KB Output is correct
5 Correct 592 ms 32844 KB Output is correct
6 Correct 825 ms 42060 KB Output is correct
7 Correct 1042 ms 54628 KB Output is correct
8 Correct 1906 ms 78944 KB Output is correct
9 Correct 3944 ms 110872 KB Output is correct
10 Correct 6018 ms 128632 KB Output is correct
11 Execution timed out 7963 ms 131072 KB Time limit exceeded (wall clock)
12 Incorrect 3299 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 3729 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 4769 ms 131072 KB Unexpected end of file - int32 expected
15 Execution timed out 6735 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 6688 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 6578 ms 131072 KB Time limit exceeded (wall clock)