oj.uz

Submission #1083718

# Submission time Handle Problem Language Result Execution time Memory
1083718 2024-09-03T21:41:27 Z rayan_bd Regions (IOI09_regions) C++17
0 / 100
 1065 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long

const int mxN = 2e5 + 5000;

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

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

void build(ll node,ll start,ll end){
	if(start==end){
		seg[node][hd[lt[start]]]=1;
		return;
	}
	ll 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(ll u=1,ll par=-1){
	st[u]=++tin;
	lt[tin]=u;
	for(auto it:adj[u]){
		if(it^par){
			dfs(it,u);
		}
	}
	en[u]=tin;
}

ll qry(ll node,ll start,ll end,ll l,ll r,ll x){
	if(start>r||end<l) return 0;
	if(start>=l&&end<=r) return seg[node][x];
	ll 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(){
	ll n,k,q,r1,r2,ans=0,super;cin>>n>>k>>q;

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

	for(ll 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() {

	//testing();

    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 18 ms 45912 KB Output isn't correct
2 Incorrect 17 ms 43864 KB Output isn't correct
3 Incorrect 20 ms 43864 KB Output isn't correct
4 Incorrect 23 ms 46168 KB Output isn't correct
5 Incorrect 25 ms 46680 KB Output isn't correct
6 Incorrect 42 ms 47968 KB Output isn't correct
7 Incorrect 63 ms 50964 KB Output isn't correct
8 Incorrect 74 ms 52820 KB Output isn't correct
9 Incorrect 166 ms 61812 KB Output isn't correct
10 Incorrect 312 ms 84460 KB Output isn't correct
11 Incorrect 1065 ms 125740 KB Output isn't correct
12 Runtime error 924 ms 131072 KB Execution killed with signal 9
13 Runtime error 527 ms 131072 KB Execution killed with signal 9
14 Runtime error 602 ms 131072 KB Execution killed with signal 9
15 Runtime error 600 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 492 ms 131072 KB Execution killed with signal 9
2 Runtime error 390 ms 131072 KB Execution killed with signal 9
3 Runtime error 315 ms 131072 KB Execution killed with signal 9
4 Runtime error 566 ms 131072 KB Execution killed with signal 9
5 Runtime error 629 ms 131072 KB Execution killed with signal 9
6 Runtime error 450 ms 131072 KB Execution killed with signal 9
7 Runtime error 326 ms 131072 KB Execution killed with signal 9
8 Runtime error 207 ms 131072 KB Execution killed with signal 9
9 Runtime error 185 ms 131072 KB Execution killed with signal 9
10 Runtime error 180 ms 131072 KB Execution killed with signal 9
11 Runtime error 191 ms 131072 KB Execution killed with signal 9
12 Runtime error 188 ms 131072 KB Execution killed with signal 9
13 Runtime error 180 ms 131072 KB Execution killed with signal 9
14 Runtime error 191 ms 131072 KB Execution killed with signal 9
15 Runtime error 178 ms 131072 KB Execution killed with signal 9
16 Runtime error 182 ms 131072 KB Execution killed with signal 9
17 Runtime error 169 ms 131072 KB Execution killed with signal 9