oj.uz

Submission #677812

# Submission time Handle Problem Language Result Execution time Memory
677812 2023-01-04T12:03:22 Z Baytoro Regions (IOI09_regions) C++17
1 / 100
 5735 ms 117756 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 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),0);
				}
			}
		}
		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:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6864 KB Output is correct
2 Incorrect 4 ms 6864 KB Output isn't correct
3 Incorrect 5 ms 6864 KB Output isn't correct
4 Incorrect 9 ms 6864 KB Output isn't correct
5 Incorrect 9 ms 6992 KB Output isn't correct
6 Incorrect 18 ms 7040 KB Output isn't correct
7 Incorrect 36 ms 7040 KB Output isn't correct
8 Incorrect 21 ms 7032 KB Output isn't correct
9 Incorrect 59 ms 7388 KB Output isn't correct
10 Incorrect 86 ms 7356 KB Output isn't correct
11 Incorrect 128 ms 7780 KB Output isn't correct
12 Incorrect 136 ms 8172 KB Output isn't correct
13 Incorrect 171 ms 8044 KB Output isn't correct
14 Incorrect 141 ms 8980 KB Output isn't correct
15 Incorrect 227 ms 10768 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 819 ms 12564 KB Output isn't correct
2 Incorrect 692 ms 11652 KB Output isn't correct
3 Incorrect 1486 ms 15252 KB Output isn't correct
4 Incorrect 308 ms 8520 KB Output isn't correct
5 Incorrect 375 ms 9680 KB Output isn't correct
6 Incorrect 1493 ms 27552 KB Output isn't correct
7 Incorrect 1830 ms 31260 KB Output isn't correct
8 Incorrect 2005 ms 56476 KB Output isn't correct
9 Incorrect 2137 ms 15484 KB Output isn't correct
10 Incorrect 5735 ms 117756 KB Output isn't correct
11 Incorrect 3832 ms 15296 KB Output isn't correct
12 Incorrect 1478 ms 20148 KB Output isn't correct
13 Incorrect 1803 ms 20192 KB Output isn't correct
14 Incorrect 2894 ms 33708 KB Output isn't correct
15 Incorrect 4768 ms 25148 KB Output isn't correct
16 Incorrect 5220 ms 28728 KB Output isn't correct
17 Incorrect 5619 ms 40512 KB Output isn't correct