oj.uz

Submission #606449

# Submission time Handle Problem Language Result Execution time Memory
606449 2022-07-26T06:46:21 Z guagua0407 Regions (IOI09_regions) C++17
100 / 100
 5456 ms 79820 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int n,r,q;
const int mxn=2e5+5;
const int mxr=25005;
const int k=38;
vector<int> adj[mxn];
int region[mxn];
int st[mxn],en[mxn];
vector<int> regioncnt[mxr];
vector<int> regiontimer[mxr];
map<int,vector<int>> ans_big;
int timer=1;

void euler_tour(int v){
	st[v]=timer;
	regiontimer[region[v]].push_back(timer);
	timer++;
	for(auto u:adj[v]){
		euler_tour(u);
	}
	en[v]=timer-1;
}

void precal(int h){
	vector<int> temp(n+2,0);
	for(auto v:regioncnt[h]){
		temp[st[v]]++;
		temp[en[v]+1]--;
	}
	ans_big[h].resize(r+1);
	for(int i=1;i<=n;i++){
		temp[i]+=temp[i-1];
	}
	for(int i=1;i<=n;i++){
		ans_big[h][region[i]]+=temp[st[i]];
	}
}

int cal_small(int r1,int r2){
	int ans=0;
	for(auto v:regioncnt[r1]){
		ans+=upper_bound(regiontimer[r2].begin(),regiontimer[r2].end(),en[v])-lower_bound(regiontimer[r2].begin(),regiontimer[r2].end(),st[v]);
	}
	return ans;
}

void query_big(int r1,int r2){
	cout<<ans_big[r1][r2]<<'\n'<<flush;
}

void query_small(int r1,int r2){
	cout<<cal_small(r1,r2)<<'\n'<<flush;
}

int main() {_
	//setIO("wayne");
	cin>>n>>r>>q;
	cin>>region[1];
	regioncnt[region[1]].push_back(1);
	for(int i=2;i<=n;i++){
		int s,h;
		cin>>s>>h;
		adj[s].push_back(i);
		region[i]=h;
		regioncnt[h].push_back(i);
	}
	euler_tour(1);
	for(int i=1;i<=r;i++){
		if(regioncnt[i].size()>=k){
			precal(i);
		}
	}
	for(int i=0;i<q;i++){
		int r1,r2;
		cin>>r1>>r2;
		if(regioncnt[r1].size()>=k){
			query_big(r1,r2);
		}
		else{
			query_small(r1,r2);
		}
	}
	return 0;
}
//maybe its multiset not set

Compilation message

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 5 ms 6124 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 10 ms 6224 KB Output is correct
6 Correct 17 ms 6224 KB Output is correct
7 Correct 31 ms 6252 KB Output is correct
8 Correct 30 ms 6224 KB Output is correct
9 Correct 85 ms 6556 KB Output is correct
10 Correct 95 ms 6736 KB Output is correct
11 Correct 186 ms 7360 KB Output is correct
12 Correct 236 ms 8352 KB Output is correct
13 Correct 308 ms 7660 KB Output is correct
14 Correct 261 ms 7968 KB Output is correct
15 Correct 338 ms 10060 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 11064 KB Output is correct
2 Correct 1181 ms 10220 KB Output is correct
3 Correct 1697 ms 12612 KB Output is correct
4 Correct 318 ms 9524 KB Output is correct
5 Correct 807 ms 17024 KB Output is correct
6 Correct 617 ms 10760 KB Output is correct
7 Correct 1187 ms 15260 KB Output is correct
8 Correct 1624 ms 30156 KB Output is correct
9 Correct 3727 ms 51056 KB Output is correct
10 Correct 5456 ms 78648 KB Output is correct
11 Correct 5026 ms 74940 KB Output is correct
12 Correct 3929 ms 55268 KB Output is correct
13 Correct 4373 ms 55100 KB Output is correct
14 Correct 4515 ms 58440 KB Output is correct
15 Correct 4467 ms 79820 KB Output is correct
16 Correct 4896 ms 73556 KB Output is correct
17 Correct 4107 ms 64468 KB Output is correct