oj.uz

Submission #1083262

# Submission time Handle Problem Language Result Execution time Memory
1083262 2024-09-02T19:47:01 Z rayan_bd Regions (IOI09_regions) C++17
0 / 100
 253 ms 131072 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 


#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())

const int mxN = 2e5 + 50;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

ll color[mxN][505];
vector<ll> adj[mxN];
ll hd[mxN];//,lt[mxN],st[mxN],en[mxN];
//ll seg[mxN*4][501],tin=-1;

/*void build(ll node,ll start,ll end){
	if(start==end){
		seg[node][lt[start]]=1;
		return;
	}
	ll mid=start+(end-start)/2;
	build(node*2+1,start,mid);
	build(node*2+2,mid+1,end);
	for(ll i=1;i<=500;++i){
		seg[node][i]=seg[node*2+1][i]+seg[node*2+2][i];
	}
}*/

/*void dfs(ll u=1,ll par=-1){
	st[u]=++tin;
	lt[tin]=hd[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 v){
	if(start>r||end<l) return 0;
	if(start>=l&&end<=r) return seg[node][v];
	ll mid=start+(end-start)/2;
	return qry(node*2+1,start,mid,l,r,v)+qry(node*2+2,mid+1,end,l,r,v);
}*/

void solve(ll tc) {
  ll n,r,q,r1,r2,h,super;cin>>n>>r>>q;
  cin>>hd[1];
  unordered_map<ll,vector<ll>> mp;
  mp[hd[1]].pb(1);
  vector<ll> out(n+1,0);
  color[1][hd[1]]=1;
  for(ll i=2;i<=n;++i){
  	cin>>super>>hd[i];
  	adj[i].pb(super);
  	mp[hd[i]].pb(i);
  	++out[super];
  	color[i][hd[i]]=1;
  }
 // memset(seg,0,sizeof(seg));
  //dfs();
  //build(0,0,tin);

  set<ll> st;
  for(ll i=1;i<=n;++i){
  	if(out[i]==0){
  		st.insert(i); 
  	}
  }

  while(st.size()){
  	ll u=*st.begin();
  	st.erase(u);
  	for(auto it:adj[u]){
  		for(ll i=1;i<505;++i){
  			color[it][i]+=color[u][i];
  		}
  		if(--out[it]==0) st.insert(it);
  	}
  }


  while(q--){
  	cin>>r1>>r2;
  	ll ans=0;
  	for(auto it:mp[hd[r1]]){
  		ans+=color[it][r2];
  		//show();
  	}
  	cout<<ans<<endl;
  }


  //cout<<color[2][2];
  //cout<<qry(0,0,tin,st[1],en[1],2)<<nl;
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    solve(0);

    return 0;
}

Compilation message

regions.cpp: In function 'void solve(long long int)':
regions.cpp:65:18: warning: unused variable 'h' [-Wunused-variable]
   65 |   ll n,r,q,r1,r2,h,super;cin>>n>>r>>q;
      |                  ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Incorrect 2 ms 5208 KB Output isn't correct
3 Incorrect 3 ms 5208 KB Output isn't correct
4 Incorrect 4 ms 5720 KB Output isn't correct
5 Incorrect 6 ms 7000 KB Output isn't correct
6 Incorrect 12 ms 8280 KB Output isn't correct
7 Incorrect 19 ms 11096 KB Output isn't correct
8 Incorrect 22 ms 13144 KB Output isn't correct
9 Incorrect 37 ms 25176 KB Output isn't correct
10 Incorrect 66 ms 45136 KB Output isn't correct
11 Incorrect 87 ms 65104 KB Output isn't correct
12 Incorrect 109 ms 85328 KB Output isn't correct
13 Incorrect 140 ms 98732 KB Output isn't correct
14 Incorrect 175 ms 125520 KB Output isn't correct
15 Runtime error 49 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 131072 KB Execution killed with signal 9
2 Runtime error 56 ms 131072 KB Execution killed with signal 9
3 Runtime error 69 ms 131072 KB Execution killed with signal 9
4 Incorrect 253 ms 122712 KB Output isn't correct
5 Runtime error 70 ms 131072 KB Execution killed with signal 9
6 Runtime error 62 ms 131072 KB Execution killed with signal 9
7 Runtime error 63 ms 131072 KB Execution killed with signal 9
8 Runtime error 59 ms 131072 KB Execution killed with signal 9
9 Runtime error 60 ms 131072 KB Execution killed with signal 9
10 Runtime error 60 ms 131072 KB Execution killed with signal 9
11 Runtime error 58 ms 131072 KB Execution killed with signal 9
12 Runtime error 58 ms 131072 KB Execution killed with signal 9
13 Runtime error 65 ms 131072 KB Execution killed with signal 9
14 Runtime error 64 ms 131072 KB Execution killed with signal 9
15 Runtime error 60 ms 131072 KB Execution killed with signal 9
16 Runtime error 61 ms 131072 KB Execution killed with signal 9
17 Runtime error 60 ms 131072 KB Execution killed with signal 9