oj.uz

Submission #53523

# Submission time Handle Problem Language Result Execution time Memory
53523 2018-06-30T07:11:56 Z 윤교준(#1420) Regions (IOI09_regions) C++11
100 / 100
 7124 ms 38064 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;

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

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

int N, K, Q;

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]]++;

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

		int cost1 = AC[r0] * 16, cost2 = (AC[r0] + AC[r1]) * 9, cost3 = AC[r1] * 16;
		int mncost = min({cost1, cost2, cost3});

		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:84: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:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:86: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:110: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 6776 KB Output is correct
2 Correct 7 ms 6836 KB Output is correct
3 Correct 9 ms 6912 KB Output is correct
4 Correct 9 ms 6996 KB Output is correct
5 Correct 13 ms 7024 KB Output is correct
6 Correct 21 ms 7152 KB Output is correct
7 Correct 40 ms 7188 KB Output is correct
8 Correct 38 ms 7280 KB Output is correct
9 Correct 44 ms 7868 KB Output is correct
10 Correct 56 ms 8024 KB Output is correct
11 Correct 138 ms 8508 KB Output is correct
12 Correct 154 ms 9148 KB Output is correct
13 Correct 241 ms 9148 KB Output is correct
14 Correct 390 ms 9532 KB Output is correct
15 Correct 283 ms 12324 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 14124 KB Output is correct
2 Correct 1650 ms 14124 KB Output is correct
3 Correct 2479 ms 17480 KB Output is correct
4 Correct 282 ms 17480 KB Output is correct
5 Correct 516 ms 17480 KB Output is correct
6 Correct 521 ms 17480 KB Output is correct
7 Correct 940 ms 17480 KB Output is correct
8 Correct 1190 ms 20416 KB Output is correct
9 Correct 2581 ms 24876 KB Output is correct
10 Correct 5637 ms 31020 KB Output is correct
11 Correct 7124 ms 31020 KB Output is correct
12 Correct 2558 ms 31020 KB Output is correct
13 Correct 2759 ms 31020 KB Output is correct
14 Correct 4040 ms 31020 KB Output is correct
15 Correct 4557 ms 32492 KB Output is correct
16 Correct 4302 ms 38064 KB Output is correct
17 Correct 4173 ms 38064 KB Output is correct