oj.uz

Submission #1083278

# Submission time Handle Problem Language Result Execution time Memory
1083278 2024-09-02T20:20:47 Z rayan_bd Regions (IOI09_regions) C++17
0 / 100
 1050 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long

const int mxN = 2e5 + 5000;

vector<int> adj[mxN];
int hd[mxN];
map<int,vector<int>> same;
vector<map<int,int>> seg(mxN*4);
int st[mxN],en[mxN],lt[mxN],tin=-1;

void answer(int ans){
	cout.flush()<<ans<<'\n';
    cout.flush();
}

void build(int node,int start,int end){
	if(start==end){
		seg[node][hd[lt[start]]]=1;
		return;
	}
	int mid=start+(end-start)/2;
	build(node*2+1,start,mid);
	build(node*2+2,mid+1,end);
	for(auto it:seg[node*2+1]) seg[node][it.first]=it.second;
	for(auto it:seg[node*2+2]) seg[node][it.first]+=it.second;
}

void dfs(int u=1,int par=-1){
	st[u]=++tin;
	lt[tin]=u;
	for(auto it:adj[u]){
		if(it^par){
			dfs(it,u);
		}
	}
	en[u]=tin;
}

int qry(int node,int start,int end,int l,int r,int x){
	if(start>r||end<l) return 0;
	if(start>=l&&end<=r) return seg[node][x];
	int mid=start+(end-start)/2;
	return qry(node*2+1,start,mid,l,r,x)+qry(node*2+2,mid+1,end,l,r,x);
}

void Solve(){
	int n,k,q,r1,r2,ans=0,super;cin>>n>>k>>q;

	cin>>hd[1];
	same[hd[1]].pb(1);

	for(int i=2;i<=n;++i){
		cin>>super>>hd[i];
		adj[i].pb(super);
		adj[super].pb(i);
		same[hd[i]].pb(i);
	}

	dfs();
	build(0,0,tin);

	while(q--){
		cin>>r1>>r2;
		ans=0;
		for(auto it:same[hd[r1]]){
			ans+=qry(0,0,tin,st[it],en[it],r2);
		}
		answer(ans);
	}
}

void testing(){
	#ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    Solve();
}

Compilation message

regions.cpp: In function 'void testing()':
regions.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen("input.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("output.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 43864 KB Output isn't correct
2 Incorrect 18 ms 43864 KB Output isn't correct
3 Incorrect 17 ms 43952 KB Output isn't correct
4 Incorrect 20 ms 44120 KB Output isn't correct
5 Incorrect 24 ms 44616 KB Output isn't correct
6 Incorrect 35 ms 47852 KB Output isn't correct
7 Incorrect 53 ms 48680 KB Output isn't correct
8 Incorrect 86 ms 50888 KB Output isn't correct
9 Incorrect 177 ms 61776 KB Output isn't correct
10 Incorrect 294 ms 82292 KB Output isn't correct
11 Incorrect 1050 ms 125920 KB Output isn't correct
12 Runtime error 919 ms 131072 KB Execution killed with signal 9
13 Runtime error 579 ms 131072 KB Execution killed with signal 9
14 Runtime error 587 ms 131072 KB Execution killed with signal 9
15 Runtime error 615 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 487 ms 131072 KB Execution killed with signal 9
2 Runtime error 370 ms 131072 KB Execution killed with signal 9
3 Runtime error 338 ms 131072 KB Execution killed with signal 9
4 Runtime error 529 ms 131072 KB Execution killed with signal 9
5 Runtime error 634 ms 131072 KB Execution killed with signal 9
6 Runtime error 430 ms 131072 KB Execution killed with signal 9
7 Runtime error 310 ms 131072 KB Execution killed with signal 9
8 Runtime error 216 ms 131072 KB Execution killed with signal 9
9 Runtime error 179 ms 131072 KB Execution killed with signal 9
10 Runtime error 198 ms 131072 KB Execution killed with signal 9
11 Runtime error 188 ms 131072 KB Execution killed with signal 9
12 Runtime error 183 ms 131072 KB Execution killed with signal 9
13 Runtime error 194 ms 131072 KB Execution killed with signal 9
14 Runtime error 202 ms 131072 KB Execution killed with signal 9
15 Runtime error 201 ms 131072 KB Execution killed with signal 9
16 Runtime error 181 ms 131072 KB Execution killed with signal 9
17 Runtime error 173 ms 131072 KB Execution killed with signal 9