oj.uz

답안 #155820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155820 2019-09-30T16:36:01 Z m1sch3f Regions (IOI09_regions) C++17
100 / 100
 5316 ms 94052 KB 

#include <bits/stdc++.h>
using namespace std;

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

using pii = pair<int,int>;
using vi = vector<int>;

const int N = 200000, R = 25000;
int C = 500;
int n,r,q;
int h[N], s[N], cnt[R];
map<int,ll> F[R];
vector<pii> points;
vector<pii> atpoints[R];
vi adj[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	cin>>n>>r>>q;
	f(i,0,n) {
		if (i) {
			cin>>s[i]; s[i]--;
			adj[i].pb(s[i]);
			adj[s[i]].pb(i);
		}
		cin>>h[i]; h[i]--;
	}
	fill(cnt,cnt+R,0);
	f(i,0,n) cnt[h[i]]++;
	int t = 0;
	function<void(int,int)> dfs = [&](int v, int p) {
		points.pb({h[v],1});
		atpoints[h[v]].pb({t++,1});
		for (int w : adj[v]) if (w != p)
			dfs(w,v);
		atpoints[h[v]].pb({t++,-1});
		points.pb({h[v],-1});
	};
	dfs(0,-1);
	// there are O(C) of these
	f(c,0,R) if (cnt[c] >= C) {
		int num = 0;
		for (pii pp : points) {
			if (pp == pii(c,1))	
				num++;
			else if (pp == pii(c,-1))
				num--;
			else if (pp.second == 1) 
				F[c][pp.first] += num;
		}			
		// there are C points or more
		num = cnt[c];
		for (pii pp : points) { 
			if (pp.first == c) {
				if (pp.second == 1) num--;
			} else F[pp.first][c] += num*pp.second;
		}
	}
	// rn, all the ones have size C have double the actual value
	f(c,0,R) if (cnt[c] >= C) for (pair<int,ll> pp : F[c]) if (cnt[pp.first] >= C)
		F[c][pp.first] /= 2;
	f(_,0,q) {
		int r1, r2;
		cin>>r1>>r2;
		r1--; r2--;
		if (!F[r1].count(r2)) {
			int c = 0;
			int i = 0, j = 0;
			F[r1][r2] = 0;
			while (j<atpoints[r2].size()) {
				if (i==atpoints[r1].size() || 
					atpoints[r1][i].first > atpoints[r2][j].first) {
					if (atpoints[r2][j++].second == 1)
						F[r1][r2] += c;
				} else c += atpoints[r1][i++].second;	
			}
		}
		cout << F[r1][r2] << endl;
		fflush(stdout);
	}


#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:132:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j<atpoints[r2].size()) {
           ~^~~~~~~~~~~~~~~~~~~~
regions.cpp:133:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i==atpoints[r1].size() || 
         ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6776 KB Output is correct
2 Correct 8 ms 6904 KB Output is correct
3 Correct 10 ms 6904 KB Output is correct
4 Correct 20 ms 6904 KB Output is correct
5 Correct 12 ms 6956 KB Output is correct
6 Correct 33 ms 7108 KB Output is correct
7 Correct 41 ms 7260 KB Output is correct
8 Correct 42 ms 7256 KB Output is correct
9 Correct 43 ms 8040 KB Output is correct
10 Correct 98 ms 8100 KB Output is correct
11 Correct 171 ms 8660 KB Output is correct
12 Correct 197 ms 9556 KB Output is correct
13 Correct 207 ms 9584 KB Output is correct
14 Correct 279 ms 10156 KB Output is correct
15 Correct 373 ms 14748 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1221 ms 15624 KB Output is correct
2 Correct 1321 ms 15112 KB Output is correct
3 Correct 2235 ms 21108 KB Output is correct
4 Correct 364 ms 11064 KB Output is correct
5 Correct 383 ms 14268 KB Output is correct
6 Correct 915 ms 27784 KB Output is correct
7 Correct 916 ms 14068 KB Output is correct
8 Correct 1205 ms 28556 KB Output is correct
9 Correct 2617 ms 28984 KB Output is correct
10 Correct 3893 ms 38068 KB Output is correct
11 Correct 4134 ms 34928 KB Output is correct
12 Correct 1393 ms 27556 KB Output is correct
13 Correct 2037 ms 30628 KB Output is correct
14 Correct 3880 ms 74244 KB Output is correct
15 Correct 3507 ms 42420 KB Output is correct
16 Correct 3389 ms 52224 KB Output is correct
17 Correct 5316 ms 94052 KB Output is correct