Submission #118006

#	Time	Username	Problem	Language	Result	Execution time	Memory
118006		IOrtroiii	Collapse (JOI18_collapse)	C++14	0 / 100	15033 ms	4336 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;

vector<int> par;
vector<int> par2;
vector<int> last;
int tt;

int find(int u) {
   if (par[u] == u) {
      return u;
   } else {
      return par[u] = find(par[u]);
   }
}

bool merge(int u, int v) {
   u = find(u);
   v = find(v);
   if (u == v) {
      return false;
   } else {
      par[v] = u;
      return true;
   }
}

int find2(int u) {
   if (last[u] != tt) {
      last[u] = tt;
      par2[u] = par[u];
   }
   if (par2[u] == u) {
      return u;
   } else {
      return par2[u] = find2(par2[u]);
   }
}

bool merge2(int u, int v) {
   u = find2(u);
   v = find2(v);
   if (u == v) {
      return true;
   } else {
      par2[v] = u;
      return true;
   }
}

vector<int> simulateCollapse(int n, vector<int> type, vector<int> from, vector<int> to, vector<int> time, vector<int> pos) {
   int m = type.size();
   int q = time.size();
   par.resize(n);
   par2.resize(n);
   last.resize(n);
   for (int i = 0; i < m; ++i) {
      if (from[i] > to[i]) {
         swap(from[i], to[i]);
      }
   }
   vector<int> go(m);
   {
      map<pair<int, int>, vector<int>> st;
      for (int i = 0; i < m; ++i) {
         auto e = make_pair(from[i], to[i]);
         if (type[i] == 0) {
            st[e].emplace_back(i);
         } else {
            go[st[e].back()] = i;
            st[e].pop_back();
         }
      }
   }
   for (int i = 0; i < m; ++i) {
      if (type[i] == 0 && go[i] == 0) {
         go[i] = m;
      }
   }
   vector<int> pref, suf;
   for (int i = 0; i < m; ++i) {
      if (type[i] == 0) {
         pref.emplace_back(i);
         suf.emplace_back(i);
      }
   }
   sort(pref.begin(), pref.end(), [&](int u, int v) {
      return to[u] < to[v];
   });
   sort(suf.begin(), suf.end(), [&](int u, int v) {
      return from[u] > from[v];
   });
   vector<vector<int>> qs(n);
   for (int i = 0; i < q; ++i) {
      qs[pos[i]].emplace_back(i);
   }
   vector<int> ans(q);
   int block = 320;
   for (int l = 0; l < m; l += block) {
      int r = min(m, l + block);
      vector<int> pref_all;
      vector<int> suf_all;
      vector<int> pref_cand;
      vector<int> suf_cand;
      for (int id : pref) {
         if (id <= l && r <= go[id]) {
            pref_all.emplace_back(id);
         } else if (id < r && l < go[id]) {
            pref_cand.emplace_back(id);
         }
      }
      for (int id : suf) {
         if (id <= l && r <= go[id]) {
            suf_all.emplace_back(id);
         } else if (id < r && l < go[id]) {
            suf_cand.emplace_back(id);
         }
      }
      vector<int> pref_qs;
      vector<int> suf_qs;
      for (int i = 0; i < n; ++i) {
         for (int id : qs[i]) {
            if (l <= time[id] && time[id] < r) {
               pref_qs.emplace_back(id);
            }
         }
      }
      for (int i = n - 1; i >= 0; --i) {
         for (int id : qs[i]) {
            if (l <= time[id] && time[id] < r) {
               suf_qs.emplace_back(id);
            }
         }
      }
      for (int i = 0; i < n; ++i) {
         par[i] = i;
      }
      {
         int ptr = 0;
         int cnt = 0;
         for (int id : pref_qs) {
            while (ptr < pref_all.size() && to[pref_all[ptr]] <= time[id]) {
               cnt += merge(from[pref_all[ptr]], to[pref_all[ptr]]);
            }
            int cnt2 = cnt;
            ++tt;
            for (int jd : pref_cand) {
               if (to[jd] <= time[id]) {
                  cnt2 += merge2(from[jd], to[jd]);
               } else {
                  break;
               }
            }
            ans[id] += (time[id] + 1 - cnt2);
         }
      }
      {
         int ptr = 0;
         int cnt = 0;
         for (int id : suf_qs) {
            while (ptr < suf_all.size() && from[suf_all[ptr]] > time[id]) {
               cnt += merge(from[suf_all[ptr]], to[suf_all[ptr]]);
               ++ptr;
            }
            int cnt2 = cnt;
            ++tt;
            for (int jd : suf_cand) {
               if (from[jd] > time[id]) {
                 cnt2 += merge2(from[jd], to[jd]);
               } else {
                  break;
               }
            }
            ans[id] += (n - 1 - time[id] - cnt2);
         }
      }
   }
   return ans;
}

Compilation message (stderr)

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:143:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr < pref_all.size() && to[pref_all[ptr]] <= time[id]) {
                    ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp:162:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr < suf_all.size() && from[suf_all[ptr]] > time[id]) {
                    ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35