Submission #907799

#TimeUsernameProblemLanguageResultExecution timeMemory
907799trMatherzRegions (IOI09_regions)C++17
21 / 100
2240 ms131072 KiB
#include <iostream> //cin, cout /* #include <fstream> std::ifstream cin ("ex.in"); std::ofstream cout ("ex.out"); */ // includes #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <vector> #include <array> #include <algorithm> #include <numeric> #include <iomanip> #include <unordered_set> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <random> #include <chrono> //usings using namespace std; using namespace __gnu_pbds; // misc #define ll long long #define pb push_back #define pq priority_queue #define ub upper_bound #define lb lower_bound template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; } template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; } typedef uint64_t hash_t; // vectors #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vppipi vector<pair<int, pair<int, int>>> #define vl vector<ll> #define vvl vector<vl> #define vvvl vector<vvl> #define vpll vector<pair<ll, ll>> #define vb vector<bool> #define vvb vector<vb> #define vs vector<string> #define sz(x) (int)x.size() #define rz resize #define all(x) x.begin(), x.end() // pairs #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define f first #define s second // sets #define si set<int> #define sl set<ll> #define ss set<string> #define in insert template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // maps #define mii map<int, int> #define mll map<ll, ll> // loops #define FR(x, z, y) for (int x = z; x < y; x++) #define FRE(x, z, y) FR(x, z, y + 1) #define F(x, y) FR(x, 0, y) #define FE(x, y) F(x, y + 1) #define A(x, y) for(auto &x : y) int n, r, q; vvi a; vvi v; vvi b; vi c; vi s, e; int ct = 0; vvi p; int sr; void dfs(int x, mii cur){ A(u, cur) p[u.f][c[x]]++; if(sz(v[c[x]]) >= sr){ if(cur.find(c[x]) == cur.end()) cur[c[x]] = 1; else cur[c[x]]++; } s[x] = ct++; b[c[x]].pb(ct - 1); A(u, a[x]) dfs(u, cur); e[x] = ct - 1; } int main(){ cin >> n >> r >> q; c = s = e = vi(n); p = vvi(r, vi(r, 0)); a = vvi(n); v = b = vvi(r); cin >> c[0]; v[--c[0]].pb(0); FR(i, 1, n){int x; cin >> x; a[--x].pb(i); cin >> c[i]; v[--c[i]].pb(i);} sr = (int) sqrt(n); mii tempm; dfs(0, tempm); while(q--){ int x, y; cin >> x >> y; x--; y--; int an = 0; if(sz(v[x]) < sr){ A(u, v[x]){ int w = e[u]; int l = s[u]; an += (ub(all(b[y]), w) - b[y].begin()) - (ub(all(b[y]), l) - b[y].begin()); } } else { an = p[x][y]; } cout << an << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...