oj.uz

Submission #152367

# Submission time Handle Problem Language Result Execution time Memory
152367 2019-09-07T19:23:30 Z groeneprof Regions (IOI09_regions) C++14
100 / 100
 6833 ms 31976 KB 
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e18;

int N, R, Q;
vector<int> par;
vector<vector<int> > children;
vector<int> region;
vector<vector<int> > sets;
vector<int> beg, en;
vector<vector<int> > prec;

void dfs0(int u, int r, int t){
	if(region[u] == r){
		t++;
	}
	else{
		prec[prec.size()-1][region[u]]+=t;
	}
	for(int v : children[u]){
		dfs0(v, r, t);
	}
}

int binsearch(int i, vector<int>& v){
	for(int j : v) H(j);
	int res = -1;
	for(int bs = 1<<20; bs>0; bs/=2){
		//H(bs);
		//H(res+bs);
		//H(v.size());
		//H(v[res+bs]);
		//H(i);
		if(res+bs < v.size() && beg[v[res+bs]] < i){
			res+=bs;
		}		
	}
	P("binsearch "<<i<<" returns "<<res);
	return res;
}

void dfs1(int u, int& stamp){
	beg[u] = stamp++;
	for(int v : children[u]){
		dfs1(v, stamp);
	}
	en[u] = stamp;
}

bool comp(int a, int b){
	return beg[a] < beg[b];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>R>>Q;
	par.resize(N,0);
	children.resize(N);
	sets.resize(R);
	region.resize(N);
	beg.resize(N);
	en.resize(N);

	cin>>region[0];
	region[0]--;
	sets[region[0]].push_back(0);
	for(int i = 1; i<N; i++){
		int a, b;
		cin>>a>>b;
		a--; b--;
		region[i]=b;
		sets[b].push_back(i);
		par[i]=a;
		children[a].push_back(i);
	}
	vector<int> bigsets(R);
	for(int i = 0; i<R;i++){
		if(sets[i].size()>500) {
			bigsets[i] = prec.size();
			prec.push_back(vector<int>(R, 0));
			dfs0(0, i, 0);
		}
	}
	{
		int stamp = 0;
		dfs1(0, stamp);
	}
	for(int i = 0; i < R; i++){
		sort(sets[i].begin(), sets[i].end(), comp);
	}

	for(int q = 0; q<Q; q++){
		int a, b;
		cin>>a>>b;
		a--; b--;

		if(sets[a].size()>500){
			cout<<prec[bigsets[a]][b]<<endl;
		}
		else{
			int res = 0;
			//P("H");
			for(int i : sets[a]){
				H(i);
				res+=binsearch(en[i], sets[b]) - binsearch(beg[i], sets[b]);
			}
			cout<<res<<endl;
		}
	}

	return 0;
}

Compilation message

regions.cpp: In function 'long long int binsearch(long long int, std::vector<long long int>&)':
regions.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(res+bs < v.size() && beg[v[res+bs]] < i){
      ~~~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 4 ms 248 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 11 ms 380 KB Output is correct
6 Correct 21 ms 376 KB Output is correct
7 Correct 33 ms 376 KB Output is correct
8 Correct 40 ms 508 KB Output is correct
9 Correct 60 ms 1016 KB Output is correct
10 Correct 85 ms 1272 KB Output is correct
11 Correct 146 ms 1784 KB Output is correct
12 Correct 167 ms 2552 KB Output is correct
13 Correct 201 ms 2424 KB Output is correct
14 Correct 304 ms 3232 KB Output is correct
15 Correct 418 ms 6200 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2344 ms 8160 KB Output is correct
2 Correct 2800 ms 7416 KB Output is correct
3 Correct 3922 ms 10604 KB Output is correct
4 Correct 291 ms 3448 KB Output is correct
5 Correct 456 ms 5328 KB Output is correct
6 Correct 1635 ms 5496 KB Output is correct
7 Correct 2138 ms 7468 KB Output is correct
8 Correct 2200 ms 13560 KB Output is correct
9 Correct 3411 ms 16408 KB Output is correct
10 Correct 6237 ms 22008 KB Output is correct
11 Correct 6833 ms 18744 KB Output is correct
12 Correct 2120 ms 19624 KB Output is correct
13 Correct 3186 ms 19856 KB Output is correct
14 Correct 4352 ms 23552 KB Output is correct
15 Correct 4697 ms 24428 KB Output is correct
16 Correct 5037 ms 29608 KB Output is correct
17 Correct 4989 ms 31976 KB Output is correct