fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "FAKERNUM"
  5. #define all(x) (x).begin(), (x).end()
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> ii;
  9.  
  10. const int MAX_N = 1e5;
  11. const int MAX_Q = 5e5;
  12. const int MOD = (int)1e9 + 7;
  13.  
  14. template <class X, class Y>
  15. bool maximize(X& x, const Y& y) {
  16.     if (x >= y) return false;
  17.     x = y;
  18.     return true;
  19. };
  20. template <class X, class Y>
  21. bool minimize(X& x, const Y& y) {
  22.     if (x <= y) return false;
  23.     x = y;
  24.     return true;
  25. };
  26.  
  27. struct Query {
  28.     int type, u, v;
  29.     ll x;
  30.     Query() {};
  31. };
  32.  
  33. int n, q, timer;
  34. int tin[MAX_N + 5], tout[MAX_N + 5], par[MAX_N + 5], depth[MAX_N + 5], id[MAX_N + 5];
  35. bool match[20][20];
  36. ll a[MAX_N + 5];
  37. vector<int> adj[MAX_N + 5];
  38. vector<Query> queries;
  39.  
  40. void preDfs(int u, int p) {
  41.     tin[u] = ++timer;
  42.     id[tin[u]] = u;
  43.     par[u] = p;
  44.     depth[u] = depth[p] + 1;
  45.  
  46.     for (int v : adj[u]) {
  47.         if (v == p) continue;
  48.         preDfs(v, u);
  49.     };
  50.  
  51.     tout[u] = timer;
  52. };
  53.  
  54. bool isAncestor(int u, int v) {
  55.     return tin[u] <= tin[v] && tout[u] >= tout[v];
  56. };
  57.  
  58. bool fakerNumber(ll x) {
  59.     string s = to_string(x);
  60.     if (count(all(s), '3') + count(all(s), '6') != s.size()) return false;
  61.  
  62.     int n = s.size();
  63.  
  64.     for (int i = 0; i < n; i++)
  65.         for (int j = 0; j < n; j++) match[i][j] = false;
  66.  
  67.     int numPalin = 0;
  68.     for (int i = 0; i < n; i++) {
  69.         match[i][i] = true;
  70.         numPalin++;
  71.     };
  72.     for (int i = 0; i + 1 < n; i++) {
  73.         match[i][i + 1] = s[i] == s[i + 1];
  74.         numPalin += match[i][i + 1];
  75.     };
  76.  
  77.     for (int l = n - 3; l >= 0; l--) {
  78.         for (int r = l + 2; r < n; r++) {
  79.             match[l][r] = match[l + 1][r - 1] && (s[l] == s[r]);
  80.             numPalin += match[l][r];
  81.         };
  82.     };
  83.  
  84.     return (double)numPalin / (n * (n + 1) / 2) > 0.5;
  85. };
  86.  
  87. namespace SUBTASK_1 {
  88.     const int N = MAX_N;
  89.     const int Q = 5000;
  90.  
  91.     ll b[MAX_N + 5];
  92.  
  93.     int subtreeQuery(int u) {
  94.         int res = 0;
  95.         for (int i = tin[u]; i <= tout[u]; i++) {
  96.             int v = id[i];
  97.             if (fakerNumber(b[v])) res++;
  98.         };
  99.         return res;
  100.     };
  101.  
  102.     int pathQuery(int u, int v) {
  103.         if (depth[u] > depth[v]) swap(u, v);
  104.  
  105.         int res = 0;
  106.         while (depth[v] != depth[u]) {
  107.             res += fakerNumber(b[v]);
  108.             v = par[v];
  109.         };
  110.  
  111.         while (u != v) {
  112.             res += fakerNumber(b[u]);
  113.             res += fakerNumber(b[v]);
  114.             u = par[u], v = par[v];
  115.         };
  116.  
  117.         res += fakerNumber(b[u]);
  118.  
  119.         return res;
  120.     };
  121.  
  122.     void updatePath(int u, int v, ll val) {
  123.         if (depth[u] > depth[v]) swap(u, v);
  124.  
  125.         while (depth[v] != depth[u]) {
  126.             b[v] += val;
  127.             v = par[v];
  128.         };
  129.  
  130.         while (u != v) {
  131.             b[u] += val;
  132.             b[v] += val;
  133.             u = par[u], v = par[v];
  134.         };
  135.  
  136.         b[u] += val;
  137.     };
  138.  
  139.     void Solve() {
  140.         for (int u = 1; u <= n; u++) b[u] = a[u];
  141.  
  142.         for (const Query& query : queries) {
  143.             int type = query.type, u = query.u;
  144.             if (type == 1) {
  145.                 int v = query.v;
  146.                 ll x = query.x;
  147.                 updatePath(u, v, x);
  148.             };
  149.             if (type == 2) {
  150.                 int v = query.v;
  151.                 cout << pathQuery(u, v) << '\n';
  152.             };
  153.             if (type == 3) {
  154.                 cout << subtreeQuery(u) << '\n';
  155.             };
  156.         };
  157.     };
  158. };  // namespace SUBTASK_1
  159.  
  160. namespace SUBTASK_2 {
  161.     const int N = MAX_N;
  162.     const int Q = MAX_Q;
  163.  
  164.     int up[N + 5][18];
  165.     int pref[N + 5], f[N + 5];
  166.  
  167.     bool checkSubtask() {
  168.         for (const Query& query : queries)
  169.             if (query.type == 1) return false;
  170.         return true;
  171.     };
  172.  
  173.     void dfs(int u) {
  174.         up[u][0] = par[u];
  175.         for (int i = 1; (1 << i) <= n; i++)
  176.             up[u][i] = up[up[u][i - 1]][i - 1];
  177.  
  178.         f[u] = f[par[u]] + fakerNumber(a[u]);
  179.  
  180.         for (int v : adj[u]) {
  181.             if (v == par[u]) continue;
  182.             dfs(v);
  183.         };
  184.     };
  185.  
  186.     int __lca(int u, int v) {
  187.         if (isAncestor(u, v)) return u;
  188.         if (isAncestor(v, u)) return v;
  189.  
  190.         for (int i = 17; i >= 0; i--)
  191.             if ((1 << i) <= n && !isAncestor(up[u][i], v))
  192.                 u = up[u][i];
  193.  
  194.         return up[u][0];
  195.     };
  196.  
  197.     void Solve() {
  198.         for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + fakerNumber(a[id[i]]);
  199.  
  200.         dfs(1);
  201.  
  202.         for (const Query& query : queries) {
  203.             int type = query.type, u = query.u;
  204.             if (type == 2) {
  205.                 int v = query.v;
  206.                 int lca = __lca(u, v);
  207.                 cout << f[u] + f[v] - 2 * f[lca] + fakerNumber(a[lca]) << '\n';
  208.             };
  209.             if (type == 3) {
  210.                 cout << pref[tout[u]] - pref[tin[u] - 1] << '\n';
  211.             };
  212.         };
  213.     };
  214. };  // namespace SUBTASK_2
  215.  
  216. int main() {
  217.     ios_base::sync_with_stdio(0);
  218.     cin.tie(0);
  219.     if (fopen(TASK ".INP", "r")) {
  220.         freopen(TASK ".INP", "r", stdin);
  221.         freopen(TASK ".OUT", "w", stdout);
  222.     };
  223.  
  224.     cin >> n >> q;
  225.     for (int u = 1; u <= n; u++) {
  226.         cin >> a[u];
  227.     };
  228.  
  229.     for (int i = 1; i < n; i++) {
  230.         int u, v;
  231.         cin >> u >> v;
  232.         adj[u].push_back(v);
  233.         adj[v].push_back(u);
  234.     };
  235.  
  236.     queries.resize(q);
  237.     for (Query& query : queries) {
  238.         cin >> query.type >> query.u;
  239.         if (query.type == 1) cin >> query.v >> query.x;
  240.         if (query.type == 2) cin >> query.v;
  241.     };
  242.  
  243.     preDfs(1, 1);
  244.  
  245.     if (SUBTASK_2::checkSubtask())
  246.         return SUBTASK_2::Solve(), 0;
  247.     SUBTASK_1::Solve();
  248.     // cout << endl;
  249. };
  250.  
Success #stdin #stdout 0.01s 7740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wDrCZH
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!