Submission #1212358

#TimeUsernameProblemLanguageResultExecution timeMemory
1212358goulthenRegions (IOI09_regions)C++20
51 / 100
8090 ms196608 KiB
//#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define rep(i, a, b) for (int i = a; i <= b; ++i) #define per(i, b, a) for (int i = b; i >= a; --i) #define pb push_back #define eb emplace_back #define all(v) (v).begin(), (v).end() #define lsb(x) (x)&(-x) void setIO(string name = "") { ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } ll fexp(ll a, ll b, ll m) { if (b == 0) return 1LL; ll p = a; ll ans = 1; while (b > 0) { if (b % 2 != 0) ans = (ans*p)%m; p = (p*p)%m; b >>= 1; } return ans; } const int MAXN = 4e5 + 10; const int INF = 1e18+5; const int MOD = 1e9+7; vector<int> g[MAXN], id[25010]; int ti[MAXN], to[MAXN], R[MAXN], dp[500][500], pfx[MAXN][500],bit[MAXN],q,n, t= 0; //WOW I guess subtask really are helpful // subtask #1 and #2 can't happen at the same time! void update(int i, int x) { for (;i <= 2*n; i += lsb(i)) bit[i] += x; } int query(int i) { int qq = 0; for (; i > 0; i -= lsb(i)) qq += bit[i]; return qq; } void dfs(int u, int p = -1) { ti[u] = t++; for (const int &v : g[u]) { if (v==p) continue; dfs(v,u); } to[u] = t++; } void smallR() { //TODO: precalc; rep(i,1,n) { pfx[to[i]][R[i]] = 1; } rep(i,1,2*n) { rep(j,1,500) { pfx[i][j] += pfx[i-1][j]; } } rep(i,1,n) { rep(j,1,500) { dp[R[i]][j] += pfx[to[i]][j] - pfx[ti[i]][j]; } } while (q--) { int a,b;cin >> a >> b; cout << dp[a][b] << endl; } } void bigR() { while (q--) { int a,b;cin >> a >> b; for (auto &i: id[b]) update(to[i],1); int ans = 0; for (auto &i: id[a]) ans += query(to[i]) - query(ti[i]); cout << ans << endl; for (auto &i: id[b]) update(to[i],-1); } } void solve() { int r;cin >> n >> r >> q; cin >> R[1]; id[R[1]].pb(1); rep(i,2,n) { int pr,rg;cin >> pr >> rg; R[i] = rg; id[rg].pb(i); g[i].pb(pr); g[pr].pb(i); } dfs(1); if (r<=500) smallR(); else bigR(); } int32_t main() { //setIO(); int tt = 1; //cin >> tt; while (tt-- > 0) solve(); }

Compilation message (stderr)

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void smallR()':
regions.cpp:85:25: warning: iteration 499 invokes undefined behavior [-Waggressive-loop-optimizations]
   85 |             dp[R[i]][j] += pfx[to[i]][j] - pfx[ti[i]][j];
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:17:40: note: within this loop
   17 | #define rep(i, a, b) for (int i = a; i <= b; ++i)
      |                                        ^
regions.cpp:84:9: note: in expansion of macro 'rep'
   84 |         rep(j,1,500) {
      |         ^~~
regions.cpp:79:23: warning: iteration 499 invokes undefined behavior [-Waggressive-loop-optimizations]
   79 |             pfx[i][j] += pfx[i-1][j];
      |             ~~~~~~~~~~^~~~~~~~~~~~~~
regions.cpp:17:40: note: within this loop
   17 | #define rep(i, a, b) for (int i = a; i <= b; ++i)
      |                                        ^
regions.cpp:78:9: note: in expansion of macro 'rep'
   78 |         rep(j,1,500) {
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...