Submission #657130

#TimeUsernameProblemLanguageResultExecution timeMemory
657130rafatoaRegions (IOI09_regions)C++17
100 / 100
7671 ms73120 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #pragma GCC optimize ("Ofast") #define double ld #define F first #define S second #define vi vector<int> #define vvi vector<vi> #define pi pair<int, int> #define vpi vector<pi> #define vb vector<bool> #define vvb vector<vb> #define pb push_back #define ppb pop_back #define read(a) for(auto &x:a) cin >> x; #define print(a) for(auto x:a) cout << x << " "; cout << "\n"; #define rs resize #define as assign #define vc vector<char> #define vvc vector<vc> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define MP make_pair #define int long long const int inf = 2e9; const int INF = 4e18; void solve(){ int n, r, q; cin >> n >> r >> q; vvi adj(n+1), R(r+1); vi h(n+1); cin >> h[1]; R[h[1]].pb(1); for(int i=2; i<=n; i++){ int p; cin >> p; adj[p].pb(i); cin >> h[i]; } vector<vpi> ac(r+1); vi in(n+1), sub(n+1); int time = 0; function<void(int)> dfs = [&](int s){ R[h[s]].pb(s); in[s] = time++; sub[s] = 1; for(auto u:adj[s]){ dfs(u); sub[s] += sub[u]; } ac[h[s]].pb({in[s], 1}); ac[h[s]].pb({in[s]+sub[s], -1}); }; dfs(1); int sq = 2*sqrt(n)/3; for(int i=1; i<=r; i++){ if(R[i].size() > sq) continue; sort(all(ac[i])); } vvi ans(r+1), ans2(r+1); for(int i=1; i<=r; i++) if(R[i].size() > sq) ans[i] = ans2[i] = vi(r+1, 0); unordered_map<int, int> mp; function<void(int)> dfs2 = [&](int s){ if(R[h[s]].size() > sq) for(auto &[el, ti]:mp) if(el != h[s]) ans[h[s]][el] += ti; mp[h[s]]++; for(auto u:adj[s]) dfs2(u); mp[h[s]]--; if(mp[h[s]] == 0) mp.erase(h[s]); }; dfs2(1); for(int i=1; i<=r; i++){ if(R[i].size() <= sq) continue; function<void(int, int)> dfs3 = [&](int s, int cnt){ if(h[s] == i) cnt++; else if(cnt > 0) ans2[i][h[s]] += cnt; for(auto u:adj[s]) dfs3(u, cnt); }; dfs3(1, 0); } while(q--){ int r1, r2; cin >> r1 >> r2; if(R[r2].size() > sq) cout << ans[r2][r1] << endl; else if(R[r1].size() > sq) cout << ans2[r1][r2] << endl; else { if(ac[r1].empty()){ cout << 0 << endl; continue; } int ans = 0, ix = 0, sum = ac[r1][ix].S; for(int i=0; i<R[r2].size(); i++){ while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S; if(ac[r1][ix].F > in[R[r2][i]]) continue; ans += sum; } cout << ans << endl; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:65:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   65 |   if(R[i].size() > sq) continue;
      |      ~~~~~~~~~~~~^~~~
regions.cpp:71:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   71 |   if(R[i].size() > sq) ans[i] = ans2[i] = vi(r+1, 0);
      |      ~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:75:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   75 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:89:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   89 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:102:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  102 |   if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:103:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  103 |   else if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:110:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:111:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...