oj.uz

Submission #677804

# Submission time Handle Problem Language Result Execution time Memory
677804 2023-01-04T11:50:09 Z Baytoro Regions (IOI09_regions) C++17
0 / 100
 1035 ms 122100 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const long long INF=1e18,mod=998244353;
int n,r,q;
const int N=2e5+5,block=25005;
int a[N],st[N],ed[N],B[N],used[block];
vector<int> g[N],e[block];
int cnt=1;
unordered_map<int,int> clc[block];
void dfs(int x){
	st[x]=cnt++;
	for(auto it: g[x]){
		dfs(it);
	}
	ed[x]=cnt-1;
}
void solve(){
	cin>>n>>r>>q>>a[1];
	for(int i=2;i<=n;i++){
		int x;cin>>x>>a[i];
		g[x].pb(i);
	}
	int b=sqrt(n);
	dfs(1);
	for(int i=1;i<=n;i++) B[st[i]]=i;
	for(int i=1;i<=n;i++) e[a[B[i]]].pb(st[B[i]]);
	for(int i=1;i<=n;i++){
		if(used[a[B[i]]]) continue;
		if((int)e[a[B[i]]].size()<=b) continue;
		used[a[B[i]]]=1;
		vector<int> pref(n+2);
		for(auto it: e[a[B[i]]]){
			int l=st[B[it]],r=ed[B[it]];
			pref[l]++;
			pref[r+1]--;
		}
		for(int j=1;j<=n;j++){
			pref[j]+=pref[j-1];
			clc[a[B[j]]][a[B[i]]]+=pref[j];
		}
	}
	while(q--){
		int a,b;cin>>a>>b;int ans=0;
		if((int)e[a].size()<=b){
			for(auto it: e[a]){
				int l=st[B[it]],r=ed[B[it]];
				auto i1=upper_bound(all(e[b]),r)-e[b].begin();
				auto i2=upper_bound(all(e[b]),l)-e[b].begin();
				if(i1){
					i1--;
					ans+=max((int)i1-i2+1,0ll);
				}
			}
		}
		else
			ans=clc[b][a];
		cout<<ans<<endl;
	}
}
main(){
	//fopn("newbarn");
	ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

regions.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~
regions.cpp: In function 'void fopn(std::string)':
regions.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6864 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6864 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6992 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6992 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6992 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6992 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6992 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 7120 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 7440 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 7696 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 8016 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 8600 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 8528 KB Time limit exceeded (wall clock)
14 Execution timed out 16 ms 9444 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 11600 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 53 ms 13532 KB Time limit exceeded (wall clock)
2 Execution timed out 52 ms 12812 KB Time limit exceeded (wall clock)
3 Execution timed out 42 ms 15380 KB Time limit exceeded (wall clock)
4 Execution timed out 11 ms 9168 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 10448 KB Time limit exceeded (wall clock)
6 Execution timed out 179 ms 28824 KB Time limit exceeded (wall clock)
7 Execution timed out 233 ms 33176 KB Time limit exceeded (wall clock)
8 Execution timed out 514 ms 58780 KB Time limit exceeded (wall clock)
9 Execution timed out 63 ms 18732 KB Time limit exceeded (wall clock)
10 Execution timed out 1035 ms 122100 KB Time limit exceeded (wall clock)
11 Execution timed out 78 ms 19932 KB Time limit exceeded (wall clock)
12 Execution timed out 113 ms 24732 KB Time limit exceeded (wall clock)
13 Execution timed out 82 ms 24868 KB Time limit exceeded (wall clock)
14 Execution timed out 340 ms 38548 KB Time limit exceeded (wall clock)
15 Execution timed out 86 ms 29764 KB Time limit exceeded (wall clock)
16 Execution timed out 81 ms 33368 KB Time limit exceeded (wall clock)
17 Execution timed out 278 ms 45304 KB Time limit exceeded (wall clock)