oj.uz

Submission #1095319

# Submission time Handle Problem Language Result Execution time Memory
1095319 2024-10-01T21:00:15 Z Saul0906 Regions (IOI09_regions) C++14
10 / 100
 123 ms 131072 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>     
#include <ext/pb_ds/tree_policy.hpp>  
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
//#define endl "\n"
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define rep2(a,b,c,d) for(ll a=b; a<c; a+=d)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(const auto &a: b)
#define multicase() int t; cin>>t; while(t--)
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define valid(c) cout<<(c ? "YES" : "NO")<<endl;
#define valid2(c,a,b) cout<<(c ? a : b)<<endl;
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define pq_max(a) priority_queue<a>
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mid ((l+r)>>1)
#define flush endl<<flush

using namespace std;
using namespace __gnu_pbds;

using vi = vector<int>;
using ll = long long;
template <typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int lim=5e5+5;
int S[lim], H[lim], tin[lim], tout[lim], ord[lim], c1[500][lim], c2[500][lim], c3[500][500], timer=1;
vector<int> adj[lim];
vector<pii> c0[lim][2];

void dfs(int u){
	tin[u]=timer++;
	c1[H[u]][tin[u]]++;
	c2[H[u]][tin[u]]++;
	repa(v,adj[u]) dfs(v);
	tout[u]=timer++;
	c2[H[u]][timer]--;
}

void dfs2(int u){
	if(H[u]<500){
		rep(i,1,500){
			c3[H[u]][i]+=(c1[i][tout[u]]-c1[i][tin[u]-1]);
		}
	}else{
		c0[H[u]][0].pb({tin[u],1});
		c0[H[u]][0].pb({tout[u]+1,-1});
		c0[H[u]][1].pb({tout[u]+1,u});
	}
	repa(v,adj[u]) dfs2(v);
}

int main(){
	fastIO();
	int N, R, Q, r1, r2;
	cin>>N>>R>>Q;
	cin>>H[1];
	pii pos[R+1];
	rep(i,1,R+1) pos[i]={0,i};
	rep(i,2,N+1){
		cin>>S[i]>>H[i];
		adj[S[i]].pb(i);
		pos[H[i]].fi++;
	}
	sort(pos+1,pos+R+1);
	reverse(pos+1,pos+R+1);
	rep(i,1,R+1) ord[pos[i].se]=i;
	rep(i,1,N+1) H[i]=ord[H[i]];
	dfs(1);
	rep(j,1,500){
		rep(i,0,timer){
			c1[j][i]+=c1[j][i-1];
			c2[j][i]+=c2[j][i-1];
			//cout<<c1[j][i]<<" "<<j<<" "<<i<<endl;
			//cout<<c2[j][i]<<" "<<j<<" "<<i<<endl;
		}
	}
	dfs2(1);
	int ans;
	while(Q--){
		cin>>r1>>r2;
		r1=ord[r1];
		r2=ord[r2];
		ans=0;
		if(r1<500 && r2<500) ans=c3[r1][r2];
		else if(r1<500){
			#define node2 c0[r2][1][i].se
			rep(i,0,c0[r2][1].size()) ans+=c2[r1][tin[node2]];
		}else if(r2<500){
			#define node1 c0[r1][1][i].se
			rep(i,0,c0[r1][1].size()) ans+=(c1[r2][tout[node1]]-c1[r2][tin[node1]-1]);
		}else{ 
			int i=0, j=0, x=0;
			#define noder1 c0[r1][0][i]
			#define noder2 c0[r2][1][j]
			while(j<c0[r2][1].size()){
				while(i<c0[r1][0].size() && noder1.fi<=noder2.fi) x+=noder1.se, i++;
				ans+=x;
				j++;
			}
		}
		cout<<ans<<endl;
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(a,b,c) for(ll a=b; a<c; a++)
......
   97 |    rep(i,0,c0[r2][1].size()) ans+=c2[r1][tin[node2]];
      |        ~~~~~~~~~~~~~~~~~~~~      
regions.cpp:97:4: note: in expansion of macro 'rep'
   97 |    rep(i,0,c0[r2][1].size()) ans+=c2[r1][tin[node2]];
      |    ^~~
regions.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(a,b,c) for(ll a=b; a<c; a++)
......
  100 |    rep(i,0,c0[r1][1].size()) ans+=(c1[r2][tout[node1]]-c1[r2][tin[node1]-1]);
      |        ~~~~~~~~~~~~~~~~~~~~      
regions.cpp:100:4: note: in expansion of macro 'rep'
  100 |    rep(i,0,c0[r1][1].size()) ans+=(c1[r2][tout[node1]]-c1[r2][tin[node1]-1]);
      |    ^~~
regions.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    while(j<c0[r2][1].size()){
      |          ~^~~~~~~~~~~~~~~~~
regions.cpp:106:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     while(i<c0[r1][0].size() && noder1.fi<=noder2.fi) x+=noder1.se, i++;
      |           ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 43860 KB Output is correct
2 Correct 26 ms 43608 KB Output is correct
3 Correct 27 ms 43864 KB Output is correct
4 Correct 27 ms 44632 KB Output is correct
5 Correct 33 ms 47448 KB Output is correct
6 Correct 33 ms 50264 KB Output is correct
7 Correct 41 ms 55384 KB Output is correct
8 Correct 48 ms 59544 KB Output is correct
9 Correct 78 ms 83548 KB Output is correct
10 Correct 123 ms 122704 KB Output is correct
11 Runtime error 66 ms 131072 KB Execution killed with signal 9
12 Runtime error 51 ms 131072 KB Execution killed with signal 9
13 Runtime error 62 ms 131072 KB Execution killed with signal 9
14 Runtime error 62 ms 131072 KB Execution killed with signal 9
15 Runtime error 56 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 131072 KB Execution killed with signal 9
2 Runtime error 64 ms 131072 KB Execution killed with signal 9
3 Runtime error 61 ms 131072 KB Execution killed with signal 9
4 Runtime error 50 ms 72956 KB Execution killed with signal 11
5 Runtime error 64 ms 73296 KB Execution killed with signal 11
6 Runtime error 60 ms 73560 KB Execution killed with signal 11
7 Runtime error 72 ms 74396 KB Execution killed with signal 11
8 Runtime error 65 ms 76112 KB Execution killed with signal 11
9 Runtime error 79 ms 77648 KB Execution killed with signal 11
10 Runtime error 70 ms 78936 KB Execution killed with signal 11
11 Runtime error 79 ms 77392 KB Execution killed with signal 11
12 Runtime error 91 ms 79440 KB Execution killed with signal 11
13 Runtime error 73 ms 78816 KB Execution killed with signal 11
14 Runtime error 74 ms 79052 KB Execution killed with signal 11
15 Runtime error 82 ms 79948 KB Execution killed with signal 11
16 Runtime error 87 ms 79916 KB Execution killed with signal 11
17 Runtime error 95 ms 79952 KB Execution killed with signal 11