Submission #545951

# Submission time Handle Problem Language Result Execution time Memory
545951 2022-04-05T16:45:59 Z cadmiumsky Collapse (JOI18_collapse) C++14
0 / 100
509 ms 524288 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;

// 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] = father(dsu[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();
      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() {
      //cout << "======\n";
      //cout << L << ' ' << R << '\n';
      //for(auto x : included)
        //cout << edge[x].first << ' ' <<edge[x].second << '\n';
      for(auto X : partial) {
        int edg, l, r;
        tie(edg, l, r) = X;
        //cout << edge[edg].first << ' ' <<edge[edg].second << '\t' << l << ' ' << r << '\n';
      }
      //for(auto x : queries)
        //cout << "?" << qs[x].first << ' ' << qs[x].second << '\n';
      //return;
      if(DSU::gettime() > n)
        DSU::init(n);
      else
        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);
        }
        //cout << qs[idx].first << ' ' << qs[idx].second << ":\n";
        //for(auto X : DSU::bk)
          //cout << X.first <<  ' ' << X.second << '\n';
        //cout <<"! " << DSU::query()  << ' ' << (n - qs[idx].second - 1) << '\n';
        rez[idx] += DSU::query() - (n - qs[idx].second - 1);
        if(DSU::gettime() > temporary)
          while(DSU::rollback() > temporary);
      }
    }
  };
  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(c + 1, c + 2));
      //cerr << "CINE\n";
      for(int i = 0; i < edge.size(); i++) {
        int ptr = 0;
        //cout << '\n'<<edge[i].first << ' ' << edge[i].second << '\n';
        for(auto X : span[i]) {
          tie(l, r) = X;
          //cout << l << ' '<< r << "--> ";
          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++)
        //cerr << qs[i].first << ' ' << B << ' ' << qs[i].first / B << '\n',
        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);
      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];
        //cout << t[i] << ' ' << 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;
        //cout << open[x][y] << '\n';
      }
      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 = sqrt(c / 2);
  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:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         while(ptr < included.size() && edge[included[ptr]].second <= time)
      |               ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:126: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]
  126 |       for(int i = 0; i < edge.size(); i++) {
      |                      ~~^~~~~~~~~~~~~
collapse.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |           if(ptr == decomp.size())
      |              ~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Incorrect 3 ms 584 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 509 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Incorrect 3 ms 584 KB Output isn't correct
4 Halted 0 ms 0 KB -