oj.uz

Submission #70697

# Submission time Handle Problem Language Result Execution time Memory
70697 2018-08-23T08:54:33 Z WA_TLE Regions (IOI09_regions) C++14
60 / 100
 4059 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(2.5*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:109: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 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 6 ms 352 KB Output is correct
4 Correct 8 ms 500 KB Output is correct
5 Correct 6 ms 548 KB Output is correct
6 Correct 14 ms 756 KB Output is correct
7 Correct 29 ms 756 KB Output is correct
8 Correct 20 ms 756 KB Output is correct
9 Correct 58 ms 1336 KB Output is correct
10 Correct 105 ms 1336 KB Output is correct
11 Correct 108 ms 1848 KB Output is correct
12 Correct 161 ms 2616 KB Output is correct
13 Correct 245 ms 2616 KB Output is correct
14 Correct 262 ms 3428 KB Output is correct
15 Correct 265 ms 44088 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 44088 KB Output is correct
2 Correct 1239 ms 44088 KB Output is correct
3 Correct 1643 ms 45976 KB Output is correct
4 Correct 241 ms 45976 KB Output is correct
5 Correct 549 ms 45976 KB Output is correct
6 Correct 745 ms 45976 KB Output is correct
7 Correct 1244 ms 45976 KB Output is correct
8 Correct 1117 ms 46284 KB Output is correct
9 Correct 2604 ms 46284 KB Output is correct
10 Runtime error 1277 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 2551 ms 131072 KB Unexpected end of file - int32 expected
12 Incorrect 1569 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 2195 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 2613 ms 131072 KB Unexpected end of file - int32 expected
15 Incorrect 4059 ms 131072 KB Unexpected end of file - int32 expected
16 Runtime error 642 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Incorrect 3723 ms 131072 KB Unexpected end of file - int32 expected