Submission #524529

#TimeUsernameProblemLanguageResultExecution timeMemory
524529AmirElarbiRegions (IOI09_regions)C++14
95 / 100
3400 ms131076 KiB
#include <bits/stdc++.h> #define vi vector<int> #define ve vector #define ll long long #define vf vector<float> #define vll vector<pair<ll,ll>> #define ii pair<int,int> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 1e9 #define eps 1e-7 #define eps1 1e-2 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 1e5+5 #define V 450 using namespace std; const int MOD = 1e9+7; const int nax = 2e5+5; const int nax2 = 3e4; vi adj[nax], node; int a[nax], tin[nax],tout[nax], cnt = 0, vis[nax2],freq[nax]; vi v[nax2]; map<int,int> res[nax2]; void dfs(int u, int p){ node.pb(u); tin[u] = cnt; cnt++; for(auto x : adj[u]) if(p != x) dfs(x,u); tout[u] = cnt-1; } int main(){ optimise; int n,r,q; cin >> n >> r >> q >> a[0]; for (int i = 1; i < n; ++i) { int b; cin >> b >> a[i]; b--; adj[i].pb(b), adj[b].pb(i); } dfs(0,0); for (int i = 0; i < n; ++i) { v[a[node[i]]].pb(i); } int mxk = sqrt(n); for (int i = 0; i < n; ++i) { if(vis[a[node[i]]]) continue; if(v[a[node[i]]].size() <= mxk) continue; vis[a[node[i]]] = 1; memset(freq,0,sizeof freq); for(auto x : v[a[node[i]]]){ int l = tin[node[x]], r = tout[node[x]]; freq[l]++, freq[r+1]--; } res[a[node[i]]][a[node[0]]] += freq[0]; for (int j = 1; j < n; ++j) { freq[j] += freq[j-1]; res[a[node[i]]][a[node[j]]] += freq[j]; } } for (int i = 0; i < q; ++i) { int xu,xv, ans = 0; cin >> xu >> xv; if(v[xu].size() <= mxk){ for(auto x : v[xu]){ int l = tin[node[x]], r = tout[node[x]]; int p1 = upper_bound(v[xv].begin(), v[xv].end(), r) - v[xv].begin(), p2 = upper_bound(v[xv].begin(), v[xv].end(), l)- v[xv].begin(); if(p1) p1--, ans += max(p1-p2+1,0); } }else ans = res[xu][xv]; cout << ans << endl; } }

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:57:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if(v[a[node[i]]].size() <= mxk) continue;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(v[xu].size() <= mxk){
      |            ~~~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...