oj.uz

답안 #677847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677847 2023-01-04T12:39:05 Z Baytoro Regions (IOI09_regions) C++17
100 / 100
 3995 ms 118492 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;

const int N=2e5+5,block=25005;
int a[N],st[N],ed[N],B[N],used[N];
vector<int> g[N],v[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;
}
int n,r,q;
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 K=sqrt(n);
	dfs(1);
	for(int i=1;i<=n;i++) B[st[i]]=i;
	for(int i=1;i<=n;i++) v[a[B[i]]].pb(st[B[i]]);
	//--------------------------------------------
	for(int i=1;i<=n;i++){
		if(used[a[B[i]]]) continue;
		if((int)v[a[B[i]]].size()<=K) continue;
		used[a[B[i]]]=1;
		int pref[n+2]{0};
		for(auto it: v[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)v[a].size()<=K){
			for(auto it: v[a]){
				int l=st[B[it]],r=ed[B[it]];
				auto i1=upper_bound(all(v[b]),r)-v[b].begin();
				auto i2=upper_bound(all(v[b]),l)-v[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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6864 KB Output is correct
2 Correct 4 ms 6864 KB Output is correct
3 Correct 4 ms 6864 KB Output is correct
4 Correct 8 ms 6864 KB Output is correct
5 Correct 12 ms 6992 KB Output is correct
6 Correct 24 ms 6992 KB Output is correct
7 Correct 30 ms 6992 KB Output is correct
8 Correct 29 ms 6992 KB Output is correct
9 Correct 47 ms 7376 KB Output is correct
10 Correct 57 ms 7496 KB Output is correct
11 Correct 120 ms 7760 KB Output is correct
12 Correct 151 ms 8236 KB Output is correct
13 Correct 152 ms 7888 KB Output is correct
14 Correct 279 ms 8516 KB Output is correct
15 Correct 346 ms 10960 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1777 ms 11624 KB Output is correct
2 Correct 2057 ms 10616 KB Output is correct
3 Correct 2842 ms 13256 KB Output is correct
4 Correct 262 ms 8428 KB Output is correct
5 Correct 388 ms 10100 KB Output is correct
6 Correct 764 ms 27668 KB Output is correct
7 Correct 1412 ms 31176 KB Output is correct
8 Correct 1734 ms 57100 KB Output is correct
9 Correct 2341 ms 15772 KB Output is correct
10 Correct 3995 ms 118492 KB Output is correct
11 Correct 3677 ms 15432 KB Output is correct
12 Correct 1386 ms 20072 KB Output is correct
13 Correct 2029 ms 19904 KB Output is correct
14 Correct 2019 ms 33480 KB Output is correct
15 Correct 3211 ms 25456 KB Output is correct
16 Correct 2943 ms 30908 KB Output is correct
17 Correct 3115 ms 42280 KB Output is correct