oj.uz

Submission #1083722

# Submission time Handle Problem Language Result Execution time Memory
1083722 2024-09-03T22:05:10 Z rayan_bd Regions (IOI09_regions) C++17
0 / 100
 75 ms 111364 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long

const int mxN = 2e5 + 5000;

ll st[mxN],en[mxN],hd[mxN],tin=-1;
set<ll> adj[mxN];
unordered_map<ll,vector<ll>> same;
unordered_map<ll,ll> seg[mxN*4];

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


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

void upd(ll node,ll start,ll end,ll idx,ll x){
	++seg[node][x];
	if(start==end) return;
	ll mid=start+(end-start)/2;
	if(idx<=mid) upd(node*2+1,start,mid,idx,x);
	else upd(node*2+2,mid+1,end,idx,x);
}

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].insert(super);
		adj[super].insert(i);
		same[hd[i]].pb(i);
	}

	dfs();

	for(ll i=1;i<=n;++i){
		upd(0,0,tin,st[i],hd[i]);
	}

	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);
		cout<<endl;
	}
}

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:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen("input.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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("output.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 111184 KB Execution killed with signal 11
2 Runtime error 74 ms 111220 KB Execution killed with signal 11
3 Runtime error 63 ms 111280 KB Execution killed with signal 11
4 Runtime error 71 ms 111184 KB Execution killed with signal 11
5 Runtime error 67 ms 111184 KB Execution killed with signal 11
6 Runtime error 67 ms 111244 KB Execution killed with signal 11
7 Runtime error 60 ms 111184 KB Execution killed with signal 11
8 Runtime error 63 ms 111184 KB Execution killed with signal 11
9 Runtime error 65 ms 111184 KB Execution killed with signal 11
10 Runtime error 71 ms 111184 KB Execution killed with signal 11
11 Runtime error 59 ms 111184 KB Execution killed with signal 11
12 Runtime error 63 ms 111184 KB Execution killed with signal 11
13 Runtime error 67 ms 111184 KB Execution killed with signal 11
14 Runtime error 66 ms 111276 KB Execution killed with signal 11
15 Runtime error 75 ms 111344 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 111364 KB Execution killed with signal 11
2 Runtime error 60 ms 111236 KB Execution killed with signal 11
3 Runtime error 74 ms 111184 KB Execution killed with signal 11
4 Runtime error 58 ms 111184 KB Execution killed with signal 11
5 Runtime error 64 ms 111188 KB Execution killed with signal 11
6 Runtime error 61 ms 111184 KB Execution killed with signal 11
7 Runtime error 62 ms 111184 KB Execution killed with signal 11
8 Runtime error 62 ms 111184 KB Execution killed with signal 11
9 Runtime error 64 ms 111184 KB Execution killed with signal 11
10 Runtime error 62 ms 111184 KB Execution killed with signal 11
11 Runtime error 61 ms 111184 KB Execution killed with signal 11
12 Runtime error 62 ms 111336 KB Execution killed with signal 11
13 Runtime error 65 ms 111240 KB Execution killed with signal 11
14 Runtime error 57 ms 111184 KB Execution killed with signal 11
15 Runtime error 62 ms 111184 KB Execution killed with signal 11
16 Runtime error 59 ms 111184 KB Execution killed with signal 11
17 Runtime error 63 ms 111356 KB Execution killed with signal 11