| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 500744 |
2022-01-01T06:53:03 Z |
cs142857 |
Regions (IOI09_regions) |
C++17 |
|
2971 ms |
29500 KB |
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
#ifdef DBG
#define dbg 1
#define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#define Dps(...) Dbgs(__VA_ARGS__)
#else
#define dbg 0
#define dpf(...) 42
#define Dps(...) 42
#endif
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;
template <typename T> inline bool UpdateMax(T& x, T v) {
if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
if(v < x) {x=v; return 1;} else return 0;
}
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
inline namespace output {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
return os << "{" << v.first << " " << v.second << "}";
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
os << "{";
bool first = 1;
REP(x, v) {
if(first) first=0; else os << " ";
os << x;
}
return os << "}";
}
} // namespace output
inline namespace output { // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}
// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); }
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; }
} // namespace output
int n, m;
VI par, home;
VI r_cnt;
int big_cnt;
vector<char> rtype;
VI rtype_cnt;
vector<int> ridx;
vector<vector<PI>> r0_subtree_dfs_range;
vector<VI> dfs_pos;
vector<VI> ans10;
vector<vector<i64>> ans11;
void Build() {
VI start(n, -1);
VI next_son(n, -1);
FOR(i, 1, n) {
next_son[i] = start[par[i]];
start[par[i]] = i;
}
ans10.assign(rtype_cnt[1], VI(rtype_cnt[0], 0));
ans11.assign(rtype_cnt[1], vector<i64>(rtype_cnt[1], 0));
r0_subtree_dfs_range.assign(rtype_cnt[0], {});
dfs_pos.assign(m, {});
FOR(i, 0, m) {
if (rtype[i] == 0) r0_subtree_dfs_range[ridx[i]].reserve(r_cnt[i]);
dfs_pos[i].reserve(r_cnt[i]);
}
VI par_r1cnt(rtype_cnt[1], 0);
VI par_r1;
int dfsn = -1;
const std::function<void(int)> Dfs = [&](int u) {
dfsn++;
int ru = home[u];
REP(p, par_r1) {
if (rtype[ru] == 0) {
ans10[ridx[p]][ridx[ru]] += par_r1cnt[ridx[p]];
} else {
ans11[ridx[p]][ridx[ru]] += par_r1cnt[ridx[p]];
}
}
if (rtype[ru] == 1) {
if (par_r1cnt[ridx[ru]]++ == 0) par_r1.pb(ru);
}
dfs_pos[ru].pb(dfsn);
int dfs_l = dfsn + 1;
for (int v = start[u]; v >= 0; v = next_son[v]) {
Dfs(v);
}
if (rtype[ru] == 1) {
if (--par_r1cnt[ridx[ru]] == 0) {
assert(par_r1.back() == ru);
par_r1.pop_back();
}
} else {
r0_subtree_dfs_range[ridx[ru]].pb({dfs_l, dfsn});
}
};
Dfs(0);
}
i64 Query(int rs, int rt) {
if (rtype[rs] == 1) {
if (rtype[rt] == 0) return ans10[ridx[rs]][ridx[rt]];
return ans11[ridx[rs]][ridx[rt]];
}
i64 res = 0;
REP(range, r0_subtree_dfs_range[ridx[rs]]) {
const auto& pos = dfs_pos[rt];
auto li = lower_bound(ALL(pos), range.first);
auto ri = upper_bound(li, pos.end(), range.second);
res += distance(li, ri);
}
return res;
}
void Solve() {
int nq;
scanf("%d%d%d",&n,&m,&nq);
par.resize(n);
home.resize(n);
scanf("%d", &home[0]);
--home[0];
FOR(i, 1, n) {
scanf("%d%d", &par[i], &home[i]);
--par[i],--home[i];
}
big_cnt = round(sqrt(n));
r_cnt.assign(n, 0);
FOR(i, 0, n) ++r_cnt[home[i]];
rtype.assign(m, 0);
ridx.assign(m, -1);
rtype_cnt.assign(2, 0);
FOR(i, 0, m) {
rtype[i] = r_cnt[i] > big_cnt;
ridx[i] = rtype_cnt[rtype[i]]++;
}
Build();
while (nq--) {
int rs,rt;
scanf("%d%d", &rs, &rt);
--rs, --rt;
printf("%lld\n", Query(rs, rt));
fflush(stdout);
}
}
int main() {
int t = 1;
// scanf("%d", &t);
for (int i = 1; i <= t; ++i) {
// printf("Case #%d: ", i);
Solve();
}
return 0;
}
Compilation message
regions.cpp: In function 'void Solve()':
regions.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d%d%d",&n,&m,&nq);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | scanf("%d", &home[0]);
| ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
189 | scanf("%d%d", &par[i], &home[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:209:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
209 | scanf("%d%d", &rs, &rt);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
200 KB |
Output is correct |
| 3 |
Correct |
3 ms |
200 KB |
Output is correct |
| 4 |
Correct |
4 ms |
200 KB |
Output is correct |
| 5 |
Correct |
6 ms |
200 KB |
Output is correct |
| 6 |
Correct |
24 ms |
272 KB |
Output is correct |
| 7 |
Correct |
32 ms |
328 KB |
Output is correct |
| 8 |
Correct |
37 ms |
272 KB |
Output is correct |
| 9 |
Correct |
39 ms |
968 KB |
Output is correct |
| 10 |
Correct |
94 ms |
584 KB |
Output is correct |
| 11 |
Correct |
127 ms |
788 KB |
Output is correct |
| 12 |
Correct |
117 ms |
1332 KB |
Output is correct |
| 13 |
Correct |
137 ms |
1052 KB |
Output is correct |
| 14 |
Correct |
228 ms |
1164 KB |
Output is correct |
| 15 |
Correct |
262 ms |
5912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1383 ms |
3856 KB |
Output is correct |
| 2 |
Correct |
1276 ms |
2656 KB |
Output is correct |
| 3 |
Correct |
2616 ms |
6592 KB |
Output is correct |
| 4 |
Correct |
244 ms |
1608 KB |
Output is correct |
| 5 |
Correct |
367 ms |
4500 KB |
Output is correct |
| 6 |
Correct |
548 ms |
4372 KB |
Output is correct |
| 7 |
Correct |
1052 ms |
5512 KB |
Output is correct |
| 8 |
Correct |
1070 ms |
15484 KB |
Output is correct |
| 9 |
Correct |
1701 ms |
8252 KB |
Output is correct |
| 10 |
Correct |
2520 ms |
27384 KB |
Output is correct |
| 11 |
Correct |
2971 ms |
9024 KB |
Output is correct |
| 12 |
Correct |
855 ms |
7696 KB |
Output is correct |
| 13 |
Correct |
1570 ms |
9412 KB |
Output is correct |
| 14 |
Correct |
1751 ms |
10392 KB |
Output is correct |
| 15 |
Correct |
2474 ms |
16192 KB |
Output is correct |
| 16 |
Correct |
2403 ms |
29500 KB |
Output is correct |
| 17 |
Correct |
2784 ms |
27576 KB |
Output is correct |
