oj.uz

Submission #152362

# Submission time Handle Problem Language Result Execution time Memory
152362 2019-09-07T19:11:51 Z groeneprof Regions (IOI09_regions) C++14
55 / 100
 6711 ms 44748 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[r][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 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 32 ms 376 KB Output is correct
8 Correct 41 ms 632 KB Output is correct
9 Correct 57 ms 1016 KB Output is correct
10 Correct 95 ms 1272 KB Output is correct
11 Correct 93 ms 1784 KB Output is correct
12 Correct 153 ms 2448 KB Output is correct
13 Correct 236 ms 2556 KB Output is correct
14 Correct 319 ms 3320 KB Output is correct
15 Correct 428 ms 6264 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 16040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 41 ms 15736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 46 ms 19236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 350 ms 3388 KB Output is correct
5 Correct 487 ms 5340 KB Output is correct
6 Correct 1676 ms 5604 KB Output is correct
7 Correct 2201 ms 7468 KB Output is correct
8 Correct 2045 ms 13648 KB Output is correct
9 Correct 3429 ms 16428 KB Output is correct
10 Correct 6711 ms 22012 KB Output is correct
11 Correct 6609 ms 18804 KB Output is correct
12 Runtime error 111 ms 41680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 114 ms 40740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 120 ms 42400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 126 ms 44748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 117 ms 44276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 119 ms 44536 KB Execution killed with signal 11 (could be triggered by violating memory limits)