/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 26ms 27.203 MiB
#2 Time Exceeded ≥1087ms ≥29.0 MiB
#3 Wrong Answer 480ms 27.422 MiB
#4 Time Exceeded ≥1087ms ≥27.723 MiB
#5 Time Exceeded ≥1093ms ≥29.094 MiB
#6 Time Exceeded ≥1091ms ≥33.754 MiB
#7 Time Exceeded ≥1097ms ≥73.832 MiB
#8 Time Exceeded ≥1100ms ≥73.848 MiB
#9 Time Exceeded ≥1101ms ≥73.832 MiB
#10 Time Exceeded ≥1091ms ≥73.844 MiB
#11 Time Exceeded ≥1094ms ≥73.801 MiB
#12 Time Exceeded ≥1081ms ≥73.824 MiB
#13 Accepted 244ms 78.012 MiB
#14 Time Exceeded ≥1101ms ≥77.887 MiB
#15 Time Exceeded ≥1095ms ≥78.0 MiB
#16 Time Exceeded ≥1098ms ≥77.945 MiB

Code

#include <bits/stdc++.h>
// #define ll long long
#define endll '\n';
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1e5 + 9;

struct node
{
   int value;
   unordered_map<int, int> mp;
};

node t[4 * N];
int lazy[4 * N];
int a[N];

node merge(node l, node r)
{ // what question need ??
   if (l.value == -1)
      return r;
   if (r.value == -1)
      return l;
   node ans;
   ans;
   for (auto i : l.mp)
   {
      ans.mp[i.first] += i.second;
   }
   for (auto i : r.mp)
   {
      ans.mp[i.first] += i.second;
   }
   return ans;
}

void build(int n, int b, int e)
{
   lazy[n] = -1;
   if (b == e)
   {
      t[n].mp[a[b]]++;
      return;
   }
   int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
   build(l, b, mid);
   build(r, mid + 1, e);
   t[n] = merge(t[l], t[r]);
}

void upd(int n, int b, int e, int i, int j, int v)
{

   if (e < i or j < b)
      return;
   if (b >= i and e <= j)
   {
      // lazy[n] = v; // set lazy
      // push(n, b, e);
      t[n].mp.clear();
      t[n].mp[a[b]]++;
      return;
   }
   int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
   upd(l, b, mid, i, j, v);
   upd(r, mid + 1, e, i, j, v);
   t[n] = merge(t[l], t[r]);
}

node query(int n, int b, int e, int i, int j)
{
   node x;
   x.value = -1;

   if (e < i or j < b)
      return x; // resutl
   if (b >= i and e <= j)
   {
      return t[n]; // result
   }
   int mid = (b + e) / 2, l = 2 * n, r = 2 * n + 1;
   return merge(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // result
}

vector<int> g[N];
int step = 1;
int start[N], endd[N];
int vis[N];
void dfs(int u, int p = 1)
{
   start[u] = step;
   vis[u] = 1;
   for (auto v : g[u])
   {
      if (vis[v] != 1)
      {
         step++;
         dfs(v, u);
      }
   }
   endd[u] = step;
}
void solve()
{

   int n;
   cin >> n;
   for (int i = 1; i <= n; i++)
   {
      char ch;
      cin >> ch;
      a[i] = ch - 'a';
   }
   for (int i = 1; i < n; i++)
   {
      int u, v;
      cin >> u >> v;
      g[u].pb(v);
      g[v].pb(u);
   }

   dfs(1);
   build(1, 1, n);
   // for (int i = 1; i <= n; i++)
   // {
   //    cout << start[i] << " " << endd[i] << endl;
   // }

   // for (int i = 1; i <= n; i++)
   // {
   //    node x = query(1, 1, n, start[i], endd[i]);
   //    for (auto j : x.mp)
   //    {
   //       cout << j.first << " " << j.second << endl;
   //    }
   //    cout << endll;
   // }
   int q;
   cin >> q;
   while (q--)
   {
      int op;
      cin >> op;
      if (op == 1)
      {
         int pos;
         char ch;

         cin >> pos >> ch;
         if (a[pos] == ch - 'a')
            continue;

         a[pos] = ch - 'a';
         upd(1, 1, n, pos, pos, ch - 'a');
      }

      else
      {

         int z;
         cin >> z;
         node x = query(1, 1, n, start[z], endd[z]);
         // cout << "For z = " << z << endll;
         // cout << start[z] << " " << endd[z] << endl;
         vector<pair<int, int>> v;

         for (auto i : x.mp)
         {
            if (i.second)
            {
               v.push_back({i.second, i.first});
            }
         }
         sort(all(v), [&](const pair<int, int> v1, const pair<int, int> v2)
              {
            if(v1.first == v2.first) {
               return v1.second < v2.second;
            }
            return v1.first > v2.first; });
         cout << char(v.front().second + 'a') << endll;
      }
   }
}

int32_t main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   int t = 1;
   // cin >> t;
   while (t--)
   {
      solve();
   }
   return 0;
}

Information

Submit By
Type
Submission
Problem
P1091 Alphabetical Kingdom
Contest
Brain Booster #5
Language
C++17 (G++ 13.2.0)
Submit At
2024-09-05 17:21:05
Judged At
2024-10-03 13:04:31
Judged By
Score
15
Total Time
≥1101ms
Peak Memory
≥78.012 MiB