oj.uz

답안 #118027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118027 2019-06-17T17:44:13 Z IOrtroiii Collapse (JOI18_collapse) C++14
0 / 100
 26 ms 4480 KB 
#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[i] == 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;
   /*
   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, n);
   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]] <= pos[id]) {
               cnt += merge(from[pref_all[ptr]], to[pref_all[ptr]]);
               ++ptr;
            }
            int cnt2 = cnt;
            ++tt;
            for (int jd : pref_cand) {
               if (jd <= time[id] && time[id] < go[jd] && to[jd] <= pos[id]) {
                  cnt2 += merge2(from[jd], to[jd]);
               }
            }
            ans[id] -= cnt2;
         }
      }
      {
         for (int i = 0; i < n; ++i) {
            par[i] = i;
         }
         int ptr = 0;
         int cnt = 0;
         for (int id : suf_qs) {
            while (ptr < suf_all.size() && from[suf_all[ptr]] > pos[id]) {
               cnt += merge(from[suf_all[ptr]], to[suf_all[ptr]]);
               ++ptr;
            }
            int cnt2 = cnt;
            ++tt;
            for (int jd : suf_cand) {
               if (jd <= time[id] && time[id] < go[jd] && from[jd] > pos[id]) {
                 cnt2 += merge2(from[jd], to[jd]);
               }
            }
            ans[id] -= cnt2;
         }
      }
   }
   return ans;
   */
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 632 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 4352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 632 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -