Submission #657212

#TimeUsernameProblemLanguageResultExecution timeMemory
657212rafatoaRegions (IOI09_regions)C++17
100 / 100
3883 ms72652 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]; 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 = sqrt(n); for(int i=1; i<=r; i++) sort(all(ac[i])); vvi ans(r+1), ans2(r+1); for(int r1=1; r1<=r; r1++){ if(R[r1].size() <= sq) continue; ans[r1] = ans2[r1] = vi(r+1, 0); //for(int r2=1; r2<=r; r2++){ // if(r1 == r2) continue; // int ix = 0, sum = ac[r2][ix].S; // for(int i=0; i<R[r1].size(); i++){ // while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S; // if(ac[r2][ix].F > in[R[r1][i]]) continue; // ans[r1][r2] += sum; // } //} } for(int r1=1; r1<=r; r1++){ if(R[r1].size() <= sq) continue; function<void(int, int)> dfs2 = [&](int s, int cnt){ if(h[s] == r1) cnt++; else if(cnt > 0) ans2[r1][h[s]] += cnt; for(auto u:adj[s]) dfs2(u, cnt); }; dfs2(1, 0); } while(q--){ int r1, r2; cin >> r1 >> r2; //if(R[r2].size() > sq) cout << ans[r2][r1] << endl; if(R[r1].size() > sq) cout << ans2[r1][r2] << endl; else { if(ac[r1].empty()){ cout << 0 << endl; continue; } int aux = 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; aux += sum; } cout << aux << endl; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); // #ifndef ONLINE_JUDGE // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // #endif solve(); return 0; }

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:67: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]
   67 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:82: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]
   82 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:96: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]
   96 |   if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:103: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]
  103 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:104: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]
  104 |     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...