oj.uz

Submission #70687

# Submission time Handle Problem Language Result Execution time Memory
70687 2018-08-23T08:35:43 Z WA_TLE Regions (IOI09_regions) C++14
16 / 100
 3406 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.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;
			//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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Incorrect 6 ms 512 KB Output isn't correct
4 Incorrect 5 ms 512 KB Output isn't correct
5 Incorrect 8 ms 512 KB Output isn't correct
6 Incorrect 18 ms 752 KB Output isn't correct
7 Incorrect 35 ms 768 KB Output isn't correct
8 Incorrect 19 ms 952 KB Output isn't correct
9 Incorrect 55 ms 3896 KB Output isn't correct
10 Incorrect 140 ms 3896 KB Output isn't correct
11 Correct 189 ms 3896 KB Output is correct
12 Incorrect 150 ms 8120 KB Output isn't correct
13 Correct 239 ms 8120 KB Output is correct
14 Correct 133 ms 8120 KB Output is correct
15 Correct 305 ms 45248 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 45248 KB Output is correct
2 Incorrect 730 ms 45248 KB Output isn't correct
3 Correct 898 ms 46024 KB Output is correct
4 Incorrect 227 ms 46024 KB Output isn't correct
5 Incorrect 419 ms 53452 KB Output isn't correct
6 Incorrect 656 ms 53452 KB Output isn't correct
7 Incorrect 1258 ms 53452 KB Output isn't correct
8 Incorrect 1943 ms 131072 KB Output isn't correct
9 Incorrect 2157 ms 131072 KB Output isn't correct
10 Runtime error 1390 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 3406 ms 131072 KB Unexpected end of file - int32 expected
12 Incorrect 1810 ms 131072 KB Unexpected end of file - int32 expected
13 Incorrect 2136 ms 131072 KB Unexpected end of file - int32 expected
14 Incorrect 2310 ms 131072 KB Unexpected end of file - int32 expected
15 Runtime error 1221 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 601 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 761 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)