Submission #519904

#TimeUsernameProblemLanguageResultExecution timeMemory
519904LptN21Regions (IOI09_regions)C++17
0 / 100
99 ms38764 KiB
#include <bits/stdc++.h> using namespace std; #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL); #define PI acos(-1.0) #define eps 1e-9 #define FF first #define SS second // VECTOR (6) #define pb push_back #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define all(v) (v).begin(), (v).end() #define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() ); // BIT (6) #define CNTBIT(x) __builtin_popcountll(x) #define ODDBIT(x) __builtin_parityll(x) #define MASK(i) (1LL<<(i)) #define BIT(x, i) (((x)>>(i))&1) #define SUBSET(big, small) (((big)&(small))==(small)) #define MINBIT(x) (x)&(-x) //typedef typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, int> ii; /* */ template<class T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } template<class T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } /* */ /* CODE BELOW */ const int N = 2e5 + 7, M = 1e9 + 7; const int oo = 1e9 + 7; const int MOD = 1e9 + 7; int n, r, q; const int BL = 206; class FenwickTree{ private: int n; vector<int> bit; public: FenwickTree(int _n = 0):n(_n) { bit.assign(_n + 1, 0); } void update(int p, int v) { for(;p<=n;p+=p&-p) { bit[p]+= v; } } int query(int l, int r) { int ans = 0; for(--l;l>0;l-=l&-l) ans-= bit[l]; for(;r>0;r-=r&-r) ans+= bit[r]; return ans; } }; FenwickTree bit(N); int in[N], out[N], cnt = 0; vector<int> adj[N]; vector<int> region[N]; int cover[N]; int ans[N], type[N]; vector<ii> R1Group[N]; vector<ii> R2Group[N]; vector<ii> naiveQuery; void dfs(int u) { region[type[u]].pb(u); in[u] = ++cnt; for(int v:adj[u]) dfs(v); out[u] = cnt; } int solve1(int u, int v) { // r1, r2 small int ans = 0; for(int x:region[v]) { bit.update(in[x], 1); } for(int x:region[u]) { ans+= bit.query(in[x], out[x]); } for(int x:region[v]) { bit.update(in[x], -1); } return ans; } void solve2() { // r1 big, r2 big/small for(int t=1;t<=r;t++) { if(sz(region[t])>M) { sort(all(R1Group[t])); for(int v:region[t]) { cover[in[v]]++; cover[out[v]+1]--; } for(int i=1;i<=n;i++) { cover[i]+= cover[i-1]; } // process query int u, idx; for(int i=0;i<sz(R1Group[t]);i++) { tie(u, idx) = R1Group[t][i]; if(i && R1Group[t][i-1].FF == u) { ans[idx] = ans[R1Group[t][i-1].SS]; continue; } for(int v:region[u]) { ans[idx]+= cover[in[v]]; } } for(int i=1;i<=n;i++) cover[i] = 0; } } } void solve3() { // r1 big/small, r2 big for(int t=1;t<=r;t++) { if(sz(region[t])>M) { sort(all(R2Group[t])); for(int v:region[t]) { cover[in[v]]++; } for(int i=1;i<=n;i++) { cover[i]+= cover[i-1]; } // process query int u, idx; for(int i=0;i<sz(R2Group[t]);i++) { tie(u, idx) = R2Group[t][i]; if(i && R2Group[t][i-1].FF == u) { ans[idx] = ans[R2Group[t][i-1].SS]; continue; } for(int v:region[u]) { ans[idx]+= cover[out[v]] - cover[in[v]-1]; } } for(int i=1;i<=n;i++) cover[i] = 0; } } } signed main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); //fastIO; scanf("%d%d%d", &n, &r, &q); int u, v; scanf("%d", &type[1]); for(int i=2;i<=n;i++) { scanf("%d%d", &u, &type[i]); adj[u].pb(i); } dfs(1); for(int i=1;i<=q;i++) { scanf("%d%d", &u, &v); if(sz(region[u])<=M&& sz(region[v])<=M) { ans[i] = solve1(u, v); } if(sz(region[u])>M) { R1Group[u].pb(ii(v, i)); } else if(sz(region[v])>M) { R2Group[v].pb(ii(u, i)); } } solve2(), solve3(); for(int i=1;i<=q;i++) { printf("%d\n", ans[i]); } return 0; }

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     scanf("%d%d%d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:170:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     int u, v; scanf("%d", &type[1]);
      |               ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d%d", &u, &type[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...