oj.uz

Submission #70690

# Submission time Handle Problem Language Result Execution time Memory
70690 2018-08-23T08:45:41 Z WA_TLE Regions (IOI09_regions) C++14
60 / 100
 2945 ms 131072 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000000;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
/*
平方分割
R2から来ている人がX以下->愚直
Xよりおおい->前計算
O(nn/X+QlogrX)
X=√(nn/Qlogr)
O(n√Qlogr)
オイラーツアー、累積和、二分探索
*/
vector<int>oya;
vector<vector<int>>ko;
vector<int>tiki;
vector<vector<pair<int,int>>>zyowa;
vector<vector<int>>maeans;
vector<int>maecode;
int maenum=0;
int dftour=0;
vector<int>dfs(int ter){
	vector<int> ret(maenum);
	if(maecode[tiki[ter]]!=-1){ret[maecode[tiki[ter]]]++;}
	zyowa[tiki[ter]].pub(mp(dftour,1));
	dftour++;
	for(auto it:ko[ter]){
		auto aaa=dfs(it);
		for(int i=0;i<maenum;i++){ret[i]+=aaa[i];}
	}
	for(int i=0;i<maenum;i++){maeans[tiki[ter]][i]+=ret[i];}
	zyowa[tiki[ter]].pub(mp(dftour,-1));
	return ret;
}
int main(void){
	int n,R,Q,i;cin>>n>>R>>Q;
	int X=sqrt(0.8*n*n/(Q*log(n)));
	zyowa.res(R);oya.res(n);tiki.res(n);
	ko.res(n);maeans.res(R);
	cin>>tiki[0];
	for(i=1;i<n;i++){cin>>oya[i]>>tiki[i];}
	for(i=0;i<n;i++){oya[i]--;tiki[i]--;if(oya[i]>=0){ko[oya[i]].pub(i);}}
	
	maecode.res(R);
	
	for(i=0;i<n;i++){maecode[tiki[i]]++;}
	
	for(i=0;i<R;i++){
		if(maecode[i]>X){maecode[i]=maenum;maenum++;}
		else{maecode[i]=-1;}
		zyowa[i].pub(mp(0,0));
	}
	for(i=0;i<R;i++){maeans[i].res(maenum);}
	
	dfs(0);
	for(i=0;i<R;i++){
		int gen=0;
		for(auto &it:zyowa[i]){gen+=it.sec;it.sec=gen;}
	}
	while(Q--){
		int a,b;cin>>a>>b;a--;b--;
		if(maecode[b]!=-1){cout<<maeans[a][maecode[b]]<<endl;continue;}
		int ans=0;
		for(i=1;i<zyowa[b].size();i++){
			if(zyowa[b][i].sec<zyowa[b][i-1].sec){continue;}
			int ter=zyowa[b][i].fir;
			//cerr<<"ter="<<ter<<endl;
			//terについて調べる
			int bas=UBI(zyowa[a],mp(ter,869120));
			ans+=zyowa[a][bas-1].sec;
		}
		cout<<ans<<endl;
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:112:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1;i<zyowa[b].size();i++){
           ~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 5 ms 436 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 19 ms 548 KB Output is correct
6 Correct 38 ms 580 KB Output is correct
7 Correct 30 ms 636 KB Output is correct
8 Correct 41 ms 764 KB Output is correct
9 Correct 42 ms 2172 KB Output is correct
10 Correct 91 ms 2172 KB Output is correct
11 Correct 131 ms 2620 KB Output is correct
12 Correct 169 ms 3768 KB Output is correct
13 Correct 135 ms 3768 KB Output is correct
14 Correct 212 ms 3768 KB Output is correct
15 Correct 304 ms 45368 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 45368 KB Output is correct
2 Correct 579 ms 45368 KB Output is correct
3 Correct 1492 ms 46084 KB Output is correct
4 Correct 366 ms 46084 KB Output is correct
5 Correct 487 ms 46084 KB Output is correct
6 Correct 752 ms 46084 KB Output is correct
7 Correct 1171 ms 46084 KB Output is correct
8 Correct 1623 ms 131072 KB Output is correct
9 Correct 2346 ms 131072 KB Output is correct
10 Runtime error 1240 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 2945 ms 131072 KB Unexpected end of file - int32 expected
12 Incorrect 1861 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 2054 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 2122 ms 131072 KB Unexpected end of file - int32 expected
15 Runtime error 1129 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 703 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 677 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)