oj.uz

Submission #545969

# Submission time Handle Problem Language Result Execution time Memory
545969 2022-04-05T18:10:36 Z cadmiumsky Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 139264 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#warning W e PREFIXUL
using namespace std;
 
// Pentru fiecare bucata de radical, avem in total N^2/B muchii incluse direct (idfk)
// Muchii care ating partial (se includ sau pe prefix suffix etc) pot fi doar O(B)
// pentru fiecare query, procesam muchiile de primul tip (compl e spusa), iar dupa punem fortat (si dupa scoatem)
// toate muchiile de al doilea tip. Astfel, la fiecare query avem compl O(Q * B).
// Wow, chiar a fost greu sa scrie si ei un editorial atat de uman (nu ca as fi eu zeu, dar mna)
 
int B;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, cmax = 1e5 + 5;
using pii = pair<int,int>;
int n, q, c;
int rollbacks = 0, forceinsert = 0, always = 0;
 
// decomp dupa POZITIE
namespace Driver {
  namespace DSU {
    int area[nmax], dsu[nmax];
    vector<pair<int,int> > bk;
    int cc;
    void init(int n) {
      for(int i = 0; i < n; i++)
        dsu[i] = i, area[i] = 1;
      bk.clear();
      cc = n;
      return;
    }
    int father(int x) {
      return (dsu[x] == x? x : father(dsu[x]));
    }
    int gettime() {return bk.size();}
    void unite(int a, int b) {
      a = father(a);
      b = father(b);
      if(a == b) 
        return;
      if(area[a] > area[b])
        swap(a, b);
      dsu[b] = a;
      area[a] += area[b];
      dsu[b] = a;
      bk.push_back({b, a});
      cc--;
    }
    int rollback() {
      if(bk.size() == 0)
        return -1;
      int a, b;
      tie(b, a) = bk.back();
      dsu[b] = b;
      area[a] -= area[b];
      cc++;
      bk.pop_back();
      //rollbacks++;
      return bk.size();
    }
    int query() { return cc; }
  }
  
  unordered_map<int, unordered_map<int,int> > atredge;
  unordered_map<int, unordered_map<int,int> > open;
  vector< pair<int,int> > edge;
  vector< vector< pair<int,int> > > span;
  vector< pair<int, int> > qs;
  vector<int> rez;
  struct Bucket {
    vector<int> included;
    vector<tuple<int,int,int> > partial;
    int L, R;
    vector<int> queries;
    Bucket(int l, int r) {tie(L, R) = {l, r};}
    void apply() {
      while(DSU::rollback() > 0);
      sort(queries.begin(), queries.end(), [&](auto x, auto y) {return qs[x].second < qs[y].second;});
      sort(included.begin(), included.end(), [&](auto x, auto y) {return edge[x].second < edge[y].second;});
      int ptr = 0;
      for(auto idx : queries) {
        int poz, time;
        tie(poz, time) = qs[idx];
        while(ptr < included.size() && edge[included[ptr]].second <= time)
          DSU::unite(edge[included[ptr]].first, edge[included[ptr]].second), ptr++;
        int temporary = DSU::gettime();
        for(auto X : partial) {
          int edg, l, r;
          tie(edg, l, r) = X;
          if(l <= poz && poz <= r && edge[edg].second <= time)
            DSU::unite(edge[edg].first, edge[edg].second);
          //always++;
        }
        rez[idx] += DSU::query() - (n - qs[idx].second - 1);
        if(DSU::gettime() > temporary)
          while(DSU::rollback() > temporary);
      }
      //forceinsert += included.size();
    }
  };
  vector<Bucket> decomp;
  namespace Init {
    void prepare() {
      int l = 0, r = min(c - 1, B - 1);
      while(l < c) {
        decomp.push_back(Bucket(l, r));
        l += B;
        r = min(c - 1, r + B);
      }
      decomp.push_back(Bucket(2 * c + 1, 2 *  c + 2));
      for(int i = 0; i < edge.size(); i++) {
        int ptr = 0;
        for(auto X : span[i]) {
          tie(l, r) = X;
          while(decomp[ptr].R < l)
            ptr++;
          if(ptr == decomp.size())
            break;
          decomp[ptr].partial.push_back({i, l, r});
          if(r <= decomp[ptr].R)
            continue;
          ptr++;
          while(l <= decomp[ptr].L && decomp[ptr].R <= r)
            decomp[ptr++].included.push_back(i);
          if(!(decomp[ptr].R < l || decomp[ptr].L > r))
            decomp[ptr].partial.push_back({i, l, r});
        }
      }
      for(int i = 0; i < q; i++)
        decomp[qs[i].first / B].queries.push_back(i);
      return;
    }
    void read(vector<int> t, vector<int>& lf, vector<int>& rh, vector<int> w, vector<int> p) {
      rez.resize(q, 0);
      for(int i = 0, ptr; i < c; i++) {
        int x, y;
        tie(x, y) = {lf[i], rh[i]};
        if(x > y)
          swap(lf[i], rh[i]), swap(x, y);
        if(atredge.find(x) == atredge.end()  || atredge[x].find(y) == atredge[x].end())
          atredge[x][y] = edge.size(), span.push_back(vector<pii>()), edge.push_back({x, y});
        ptr = atredge[x][y];
        open[x][y];
        if(open[x][y] == 0)
          span[ptr].push_back({i, -1});
        open[x][y] += -2 * t[i] + 1;
        if(open[x][y] == 0)
          span[ptr].back().second = i - 1;
      }
      int x, y, val;
      for(auto X : open) {
        x = X.first;
        for(auto Y : X.second) {
          tie(y, val) = Y;
          if(val > 0)
            span[atredge[x][y]].back().second = c - 1;
        }
      }
      for(int i = 0; i < q; i++)
        qs.push_back({w[i], p[i]});
      return;
    }
  }
  namespace Decomp {
    void start() {
      for(auto& x : decomp)
        x.apply();
    }
  }
  void erase() {
    DSU::init(n);
    decomp.clear();
    span.clear();
    qs.clear();
    edge.clear();
    atredge.clear();
    open.clear();
  }
}
 
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
  n = N;
  c = T.size();
  q = W.size();
  B = 220;
  Driver::DSU::init(n);
  Driver::Init::read(T, X, Y, W, P);
  Driver::Init::prepare();
  Driver::Decomp::start();
  Driver::erase();
  for(int i = 0; i < c; i++) {
    X[i] = N - X[i] - 1; 
    Y[i] = N - Y[i] - 1; 
  }
  for(int i = 0; i < q; i++)
    P[i] = N - P[i] - 2;
  Driver::Init::read(T, X, Y, W, P);
  Driver::Init::prepare();
  Driver::Decomp::start();
  return Driver::rez;
}

Compilation message

collapse.cpp:3:2: warning: #warning W e PREFIXUL [-Wcpp]
    3 | #warning W e PREFIXUL
      |  ^~~~~~~
collapse.cpp: In member function 'void Driver::Bucket::apply()':
collapse.cpp:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         while(ptr < included.size() && edge[included[ptr]].second <= time)
      |               ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |       for(int i = 0; i < edge.size(); i++) {
      |                      ~~^~~~~~~~~~~~~
collapse.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |           if(ptr == decomp.size())
      |              ~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 564 KB Output is correct
5 Correct 9 ms 724 KB Output is correct
6 Correct 87 ms 1812 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 10 ms 1784 KB Output is correct
10 Correct 92 ms 1748 KB Output is correct
11 Correct 131 ms 2892 KB Output is correct
12 Correct 991 ms 2916 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4172 KB Output is correct
2 Correct 36 ms 4172 KB Output is correct
3 Correct 177 ms 8280 KB Output is correct
4 Correct 53 ms 4232 KB Output is correct
5 Correct 308 ms 9352 KB Output is correct
6 Correct 816 ms 5456 KB Output is correct
7 Execution timed out 15035 ms 139264 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4172 KB Output is correct
2 Correct 39 ms 4164 KB Output is correct
3 Correct 48 ms 4172 KB Output is correct
4 Correct 59 ms 4256 KB Output is correct
5 Correct 650 ms 4476 KB Output is correct
6 Correct 1301 ms 5460 KB Output is correct
7 Execution timed out 15090 ms 79364 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 564 KB Output is correct
5 Correct 9 ms 724 KB Output is correct
6 Correct 87 ms 1812 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 10 ms 1784 KB Output is correct
10 Correct 92 ms 1748 KB Output is correct
11 Correct 131 ms 2892 KB Output is correct
12 Correct 991 ms 2916 KB Output is correct
13 Correct 30 ms 4172 KB Output is correct
14 Correct 36 ms 4172 KB Output is correct
15 Correct 177 ms 8280 KB Output is correct
16 Correct 53 ms 4232 KB Output is correct
17 Correct 308 ms 9352 KB Output is correct
18 Correct 816 ms 5456 KB Output is correct
19 Execution timed out 15035 ms 139264 KB Time limit exceeded
20 Halted 0 ms 0 KB -