oj.uz

Submission #606504

# Submission time Handle Problem Language Result Execution time Memory
606504 2022-07-26T06:55:00 Z guagua0407 Regions (IOI09_regions) C++17
100 / 100
 5480 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=37;
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 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 12 ms 6108 KB Output is correct
6 Correct 23 ms 6224 KB Output is correct
7 Correct 26 ms 6224 KB Output is correct
8 Correct 38 ms 6224 KB Output is correct
9 Correct 53 ms 6608 KB Output is correct
10 Correct 75 ms 6736 KB Output is correct
11 Correct 194 ms 7264 KB Output is correct
12 Correct 285 ms 8152 KB Output is correct
13 Correct 332 ms 7816 KB Output is correct
14 Correct 293 ms 8052 KB Output is correct
15 Correct 316 ms 9980 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 10892 KB Output is correct
2 Correct 1139 ms 10092 KB Output is correct
3 Correct 1697 ms 12760 KB Output is correct
4 Correct 317 ms 9496 KB Output is correct
5 Correct 585 ms 16984 KB Output is correct
6 Correct 645 ms 10812 KB Output is correct
7 Correct 1116 ms 15252 KB Output is correct
8 Correct 1690 ms 30192 KB Output is correct
9 Correct 3477 ms 51104 KB Output is correct
10 Correct 5480 ms 78592 KB Output is correct
11 Correct 4899 ms 74940 KB Output is correct
12 Correct 3762 ms 55172 KB Output is correct
13 Correct 4022 ms 55092 KB Output is correct
14 Correct 3934 ms 58448 KB Output is correct
15 Correct 4091 ms 79820 KB Output is correct
16 Correct 4781 ms 73592 KB Output is correct
17 Correct 3981 ms 64484 KB Output is correct