oj.uz

Submission #53522

# Submission time Handle Problem Language Result Execution time Memory
53522 2018-06-30T07:08:28 Z 윤교준(#1420) Regions (IOI09_regions) C++11
65 / 100
 7785 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;

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];
vector<int> DIV[MAXK+1], DIN[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 i = 1; i <= N; i++) {
		DIV[A[i]].pb(di[i]);
		DIN[A[i]].pb(di[i]+cnt[i]);
	}
	for(int i = 1; i <= K; i++) {
		sorv(DIV[i]);
		sorv(DIN[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;
		}

		int cost0 = ACRO[r0] <= T ? AC[r1] : INF, cost1 = AC[r0] * 16, cost2 = (AC[r0] + AC[r1]) * 9, cost3 = AC[r1] * 16;
		int mncost = min({cost0, cost1, cost2, cost3});

		if(ACRO[r0] <= T && mncost == cost0) { // cost0
			int ret = 0;
			for(int v : AV[r1])
				ret += UpSum[v][ACRO[r0]];
			printf("%d\n", MP[key] = ret);
			fflush(stdout);
			continue;
		}
		if(mncost == cost1) {
			int ret = 0;
			for(int v : AV[r0])
				ret += (int)(upper_bound(allv(DIV[r1]), di[v]+cnt[v]-1)
							- upper_bound(allv(DIV[r1]), di[v]));
			printf("%d\n", MP[key] = ret);
			fflush(stdout);
			continue;
		}

		if(mncost == cost2) {
			// cost2
			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);
		}

		// cost3
		{
			int ret = 0;
			for(int v : AV[r1]) {
				ret += (int)(upper_bound(allv(DIV[r0]), di[v]) - DIV[r0].begin());
				ret -= (int)(upper_bound(allv(DIN[r0]), di[v]) - DIN[r0].begin());
			}
			printf("%d\n", MP[key] = ret);
			fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:131: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:91: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:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:93: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:162: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 10 ms 6776 KB Output is correct
2 Correct 7 ms 6964 KB Output is correct
3 Correct 8 ms 6964 KB Output is correct
4 Correct 11 ms 7100 KB Output is correct
5 Correct 13 ms 7404 KB Output is correct
6 Correct 26 ms 7708 KB Output is correct
7 Correct 34 ms 8148 KB Output is correct
8 Correct 44 ms 8608 KB Output is correct
9 Correct 38 ms 10700 KB Output is correct
10 Correct 93 ms 13676 KB Output is correct
11 Correct 182 ms 16856 KB Output is correct
12 Correct 155 ms 20268 KB Output is correct
13 Correct 265 ms 22508 KB Output is correct
14 Correct 498 ms 26332 KB Output is correct
15 Correct 461 ms 34724 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 55772 KB Output is correct
2 Correct 1995 ms 57448 KB Output is correct
3 Correct 2596 ms 67600 KB Output is correct
4 Correct 435 ms 67600 KB Output is correct
5 Correct 520 ms 67600 KB Output is correct
6 Correct 799 ms 67600 KB Output is correct
7 Correct 1302 ms 67600 KB Output is correct
8 Correct 1709 ms 76100 KB Output is correct
9 Correct 3048 ms 107908 KB Output is correct
10 Correct 4701 ms 125400 KB Output is correct
11 Execution timed out 7785 ms 131072 KB Time limit exceeded (wall clock)
12 Incorrect 2941 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 3262 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 3907 ms 131072 KB Unexpected end of file - int32 expected
15 Incorrect 5117 ms 131072 KB Unexpected end of file - int32 expected
16 Incorrect 4654 ms 131072 KB Unexpected end of file - int32 expected
17 Incorrect 4566 ms 131072 KB Unexpected end of file - int32 expected