Submission #545965

# Submission time Handle Problem Language Result Execution time Memory
545965 2022-04-05T17:50:30 Z cadmiumsky Collapse (JOI18_collapse) C++14
Compilation error
0 ms 0 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 onrollback = 0, oninsertion = 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();
      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() {
      //cerr << max((int)partial.size() - B, 0)  << '\n';
      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);
        }
        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(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 = 600;
  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;
}

int main(int argc, char *argv[]) {
	int N, C, Q;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}

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:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         while(ptr < included.size() && edge[included[ptr]].second <= time)
      |               ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:109: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]
  109 |       for(int i = 0; i < edge.size(); i++) {
      |                      ~~^~~~~~~~~~~~~
collapse.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |           if(ptr == decomp.size())
      |              ~~~~^~~~~~~~~~~~~~~~
collapse.cpp: In function 'int main(int, char**)':
collapse.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |  scanf("%d%d%d", &N, &C, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |   scanf("%d%d%d", &T[i], &X[i], &Y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |   scanf("%d%d", &W[i], &P[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccZkdsKO.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQKVcOL.o:collapse.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status