oj.uz

답안 #677828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677828 2023-01-04T12:23:21 Z Baytoro Regions (IOI09_regions) C++17
1 / 100
 6218 ms 119256 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
//const long long INF=1e18,mod=998244353;
int n,r,q;
const int N=2e5+5,block=25005;
int a[N],st[N],ed[N],B[N],used[N];
vector<int> g[N],e[block];
int cnt=1;
unordered_map<int,int> clc[block];
void dfs(int x, int p=-1){
	st[x]=cnt++;
	for(auto it: g[x]){
		if(it==p) continue;
		dfs(it,x);
	}
	ed[x]=cnt-1;
}
void solve(){
	cin>>n>>r>>q>>a[1];
	for(int i=2;i<=n;i++){
		int x;cin>>x>>a[i];
		g[x].pb(i);
	}
	int b=sqrt(n);
	dfs(1);
	for(int i=1;i<=n;i++) B[st[i]]=i;
	for(int i=1;i<=n;i++) e[a[B[i]]].pb(st[B[i]]);
	for(int i=1;i<=n;i++){
		if(used[a[B[i]]]) continue;
		if((int)e[a[B[i]]].size()<=b) continue;
		used[a[B[i]]]=1;
		vector<int> pref(n+2,0);
		for(auto it: e[a[B[i]]]){
			int l=st[B[it]],r=ed[B[it]];
			pref[l]++;
			pref[r+1]--;
		}
		for(int j=1;j<=n;j++){
			pref[j]+=pref[j-1];
			clc[a[B[j]]][a[B[i]]]+=pref[j];
		}
	}
	while(q--){
		int a,b;cin>>a>>b;
		int ans=0;
		if((int)e[a].size()<=b){
			for(auto it: e[a]){
				int l=st[B[it]],r=ed[B[it]];
				auto i1=upper_bound(all(e[b]),r)-e[b].begin();
				auto i2=upper_bound(all(e[b]),l)-e[b].begin();
				if(i1){
					ans+=max((int)(i1-i2),0);
				}
			}
		}
		else
			ans=clc[b][a];
		cout<<ans<<endl;
	}
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

regions.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~
regions.cpp: In function 'void fopn(std::string)':
regions.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6864 KB Output is correct
2 Incorrect 4 ms 6884 KB Output isn't correct
3 Incorrect 5 ms 6864 KB Output isn't correct
4 Incorrect 8 ms 6864 KB Output isn't correct
5 Incorrect 10 ms 6992 KB Output isn't correct
6 Incorrect 23 ms 7064 KB Output isn't correct
7 Incorrect 35 ms 6992 KB Output isn't correct
8 Incorrect 38 ms 6992 KB Output isn't correct
9 Incorrect 46 ms 7480 KB Output isn't correct
10 Incorrect 86 ms 7376 KB Output isn't correct
11 Incorrect 120 ms 7880 KB Output isn't correct
12 Incorrect 145 ms 8248 KB Output isn't correct
13 Incorrect 95 ms 8008 KB Output isn't correct
14 Incorrect 184 ms 8876 KB Output isn't correct
15 Incorrect 242 ms 11380 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 841 ms 12884 KB Output isn't correct
2 Incorrect 923 ms 11624 KB Output isn't correct
3 Incorrect 1377 ms 15868 KB Output isn't correct
4 Incorrect 270 ms 8524 KB Output isn't correct
5 Incorrect 282 ms 10144 KB Output isn't correct
6 Incorrect 1517 ms 27616 KB Output isn't correct
7 Incorrect 1875 ms 31416 KB Output isn't correct
8 Incorrect 2054 ms 57572 KB Output isn't correct
9 Incorrect 2290 ms 15916 KB Output isn't correct
10 Incorrect 6046 ms 119256 KB Output isn't correct
11 Incorrect 4334 ms 15420 KB Output isn't correct
12 Incorrect 1434 ms 20208 KB Output isn't correct
13 Incorrect 1957 ms 20404 KB Output isn't correct
14 Incorrect 2615 ms 33840 KB Output isn't correct
15 Incorrect 4742 ms 26248 KB Output isn't correct
16 Incorrect 5390 ms 31716 KB Output isn't correct
17 Incorrect 6218 ms 43128 KB Output isn't correct