Submission #764194

#TimeUsernameProblemLanguageResultExecution timeMemory
764194a_aguiloRegions (IOI09_regions)C++14
40 / 100
8101 ms25276 KiB
#include<bits/stdc++.h> using namespace std; int N, R, Q; int SQRT = 450; int region[200000]; vector<vector<int>> AdjList; vector<int> EulerTours; int enter[200000]; int out[200000]; //unordered_map<int, int> freqRegions; void dfs(int node){ //cout << node << endl; EulerTours.push_back(node); enter[node] = EulerTours.size()-1; for(int son: AdjList[node]){ dfs(son); } out[node] = EulerTours.size()-1; } /* void rSmall(){ int r; freqRegions.reserve(512); vector<vector<int>> dp(R, vector<int>(R, 0)); preProcess(0, dp); int r1, r2; while(Q--){ cin >> r1 >> r2; r1--; r2--; cout << dp[r1][r2] << endl; } }*/ void rBig(){ //vector<map<int, int>> blocks(500); vector<vector<int>> employees(R); for(int i = 0; i < N; ++i){ employees[region[i]].push_back(i); int B = i/SQRT; //blocks[R][region[EulerTours[i]]]++; } int r1, r2; while(Q--){ cin >> r1 >> r2; r1--; r2--; int ans = 0; for(int i: employees[r1]){ for(int j: employees[r2]){ if(enter[i]<enter[j] && out[i]>=out[j])ans++; } } cout << ans << endl; } } int main(){ int p; cin >> N >> R >> Q; AdjList = vector<vector<int>>(N); for(int i = 0; i < N; ++i){ if(i){ cin >> p; p--; AdjList[p].push_back(i); } cin >> region[i]; region[i]--; } dfs(0); /* for(int i = 0; i < N; ++i) cout << EulerTours[i] << " "; cout << endl;*/ /* if(R <= 1000) rSmall(); else rBig();*/ rBig(); return 0; }

Compilation message (stderr)

regions.cpp: In function 'void rBig()':
regions.cpp:44:7: warning: unused variable 'B' [-Wunused-variable]
   44 |   int B = i/SQRT;
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...