oj.uz

답안 #118014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118014 2019-06-17T16:44:08 Z IOrtroiii Collapse (JOI18_collapse) C++14
0 / 100
 566 ms 5872 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 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);
            }
         }
      }
      assert(pref_all.size() == suf_all.size());
      assert(pref_cand.size() == suf_cand.size());
      assert(pref_qs.size() == suf_qs.size());
      {
         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] += (pos[id] + 1 - 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] += (n - 1 - pos[id] - cnt2);
         }
      }
   }
   return ans;
}

Compilation message

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:146:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr < pref_all.size() && to[pref_all[ptr]] <= pos[id]) {
                    ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp:167:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr < suf_all.size() && from[suf_all[ptr]] > pos[id]) {
                    ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3832 KB Output is correct
2 Correct 32 ms 3832 KB Output is correct
3 Incorrect 566 ms 5872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

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