oj.uz

Submission #1083277

# Submission time Handle Problem Language Result Execution time Memory
1083277 2024-09-02T20:17:11 Z rayan_bd Regions (IOI09_regions) C++17
0 / 100
 1254 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
}

int main() {
    
	//testing();

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    Solve();

    return 0;
}

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 19 ms 43608 KB Output isn't correct
2 Incorrect 27 ms 43608 KB Output isn't correct
3 Incorrect 20 ms 43864 KB Output isn't correct
4 Incorrect 32 ms 43816 KB Output isn't correct
5 Incorrect 29 ms 44632 KB Output isn't correct
6 Incorrect 38 ms 45656 KB Output isn't correct
7 Incorrect 56 ms 48464 KB Output isn't correct
8 Incorrect 86 ms 50712 KB Output isn't correct
9 Incorrect 184 ms 61796 KB Output isn't correct
10 Incorrect 357 ms 82664 KB Output isn't correct
11 Incorrect 1254 ms 125868 KB Output isn't correct
12 Runtime error 1139 ms 131072 KB Execution killed with signal 9
13 Runtime error 646 ms 131072 KB Execution killed with signal 9
14 Runtime error 767 ms 131072 KB Execution killed with signal 9
15 Runtime error 758 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 602 ms 131072 KB Execution killed with signal 9
2 Runtime error 502 ms 131072 KB Execution killed with signal 9
3 Runtime error 361 ms 131072 KB Execution killed with signal 9
4 Runtime error 644 ms 131072 KB Execution killed with signal 9
5 Runtime error 734 ms 131072 KB Execution killed with signal 9
6 Runtime error 552 ms 131072 KB Execution killed with signal 9
7 Runtime error 389 ms 131072 KB Execution killed with signal 9
8 Runtime error 236 ms 131072 KB Execution killed with signal 9
9 Runtime error 210 ms 131072 KB Execution killed with signal 9
10 Runtime error 210 ms 131072 KB Execution killed with signal 9
11 Runtime error 210 ms 131072 KB Execution killed with signal 9
12 Runtime error 218 ms 131072 KB Execution killed with signal 9
13 Runtime error 220 ms 131072 KB Execution killed with signal 9
14 Runtime error 238 ms 131072 KB Execution killed with signal 9
15 Runtime error 204 ms 131072 KB Execution killed with signal 9
16 Runtime error 198 ms 131072 KB Execution killed with signal 9
17 Runtime error 200 ms 131072 KB Execution killed with signal 9