oj.uz

Submission #152364

# Submission time Handle Problem Language Result Execution time Memory
152364 2019-09-07T19:16:28 Z groeneprof Regions (IOI09_regions) C++14
55 / 100
 6435 ms 64332 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][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>(N, 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 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 26 ms 376 KB Output is correct
7 Correct 32 ms 504 KB Output is correct
8 Correct 37 ms 504 KB Output is correct
9 Correct 59 ms 1144 KB Output is correct
10 Correct 62 ms 1272 KB Output is correct
11 Correct 138 ms 1800 KB Output is correct
12 Correct 169 ms 2552 KB Output is correct
13 Correct 231 ms 2424 KB Output is correct
14 Correct 354 ms 3240 KB Output is correct
15 Correct 337 ms 6264 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2134 ms 15128 KB Output isn't correct
2 Incorrect 2537 ms 15604 KB Output isn't correct
3 Incorrect 3937 ms 17640 KB Output isn't correct
4 Correct 368 ms 3320 KB Output is correct
5 Correct 475 ms 5372 KB Output is correct
6 Correct 1563 ms 5604 KB Output is correct
7 Correct 2176 ms 7464 KB Output is correct
8 Correct 2009 ms 13648 KB Output is correct
9 Correct 3305 ms 16304 KB Output is correct
10 Correct 6354 ms 22116 KB Output is correct
11 Correct 6435 ms 18868 KB Output is correct
12 Incorrect 2136 ms 22312 KB Output isn't correct
13 Incorrect 2602 ms 22576 KB Output isn't correct
14 Incorrect 4003 ms 54396 KB Output isn't correct
15 Incorrect 5099 ms 26932 KB Output isn't correct
16 Incorrect 5412 ms 32468 KB Output isn't correct
17 Incorrect 5020 ms 64332 KB Output isn't correct