Submission #118028

#	Time	Username	Problem	Language	Result	Execution time	Memory
118028		IOrtroiii	Collapse (JOI18_collapse)	C++14	5 / 100	15055 ms	10360 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 false;
   } 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.assign(n, 0);
   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>, int> st;
      for (int i = 0; i < m; ++i) {
         pair<int, int> e = make_pair(from[i], to[i]);
         if (type[i] == 0) {
            st[e] = i;
         } else {
            assert(st.count(e));
            go[st[e]] = i;
            st.erase(e);
         }
      }
      for (auto p : st) {
         go[p.second] = m;
      }
   }
   vector<int> ans(q);
   for (int i = 0; i < q; ++i) {
      int ncomp = n;
      for (int j = 0; j < n; ++j) {
         par[j] = j;
      }
      for (int j = 0; j < m; ++j) {
         if (type[j] == 0 && j <= time[i] && time[i] < go[j]) {
            if (to[j] <= pos[i] || from[j] > pos[i]) {
               ncomp -= merge(from[j], to[j]);
            }
         }
      }
      ans[i] = ncomp;
   }
   return ans;
}

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